ds练习

spoj10628

强制在线，树上路径上第k小权值。

典中典之权值线段树，要离散化，没给数的范围，被坑麻了qwq

 1 #include
 2 #include
 3 #include
 4 #include
 5 using namespace std;
 6 const int N=1e5+10;
 7 int nd=0,tot=0,n;
 8 int he[N],ne[N*2],t[N*2];
 9 int dep[N],f[N][20];
10 int fr[N],tr[N*80],ch[N*80][2];
11 int a[N],c[N];
12 void link(int x,int y)
13 {
14     tot++;
15     ne[tot]=he[x];
16     he[x]=tot;
17     t[tot]=y;    
18 }
19 int lca(int x,int y)
20 {
21     if (dep[x]<dep[y]) swap(x,y);
22     for (int i=19;i>=0;i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i];
23     if (x==y) return x;
24     for (int i=19;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
25     return f[x][0];    
26 }
27 void ins(int r1,int r2,int l,int r,int x)
28 {
29     if (l==r) 
30     {
31         tr[r1]++;
32         return;
33     }
34     int mid=l+r>>1;
35     if (x<=mid)
36     {
37         if (!ch[r1][0]) ch[r1][0]=++nd;
38         ch[r1][1]=ch[r2][1];
39         ins(ch[r1][0],ch[r2][0],l,mid,x);
40     }else
41     {
42         if (!ch[r1][1]) ch[r1][1]=++nd;
43         ch[r1][0]=ch[r2][0];
44         ins(ch[r1][1],ch[r2][1],mid+1,r,x);
45     }
46     tr[r1]=tr[ch[r1][0]]+tr[ch[r1][1]];
47 }
48 void dfs(int x,int y)
49 {
50     dep[x]=dep[y]+1;
51     f[x][0]=y;
52     for (int i=1;i<=19;i++) f[x][i]=f[f[x][i-1]][i-1];
53     fr[x]=++nd;
54     ins(fr[x],fr[y],1,n,c[x]);
55     for (int i=he[x];i;i=ne[i]) if (t[i]!=y) dfs(t[i],x);    
56 }
57 int query(int a,int b,int c,int d,int l,int r,int x)
58 {
59     if (l==r) return l;
60     int mid=l+r>>1,tmp=tr[ch[c][0]]+tr[ch[d][0]]-tr[ch[a][0]]-tr[ch[b][0]];
61     if (tmp>=x) return query(ch[a][0],ch[b][0],ch[c][0],ch[d][0],l,mid,x);
62     return query(ch[a][1],ch[b][1],ch[c][1],ch[d][1],mid+1,r,x-tmp);
63 }
64 struct aa
65 {
66     int x,y;    
67 }b[N];
68 bool cmp(aa x,aa y)
69 {
70     return x.x<y.x;    
71 }
72 int main()
73 {
74     //freopen("test.in","r",stdin);
75     int m;
76     scanf("%d%d",&n,&m);
77     for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i].x=a[i],b[i].y=i;
78     sort(b+1,b+n+1,cmp);
79     for (int i=1;i<=n;i++) c[b[i].y]=i;
80     for (int i=1;i) 
81     {
82         int x,y;
83         scanf("%d%d",&x,&y);
84         link(x,y);
85         link(y,x);
86     }
87     dfs(1,0);
88     int lastans=0;
89     for (int i=1;i<=m;i++) 
90     {
91         int x,y,k;
92         scanf("%d%d%d",&x,&y,&k);
93         x=x^lastans;
94         int z=lca(x,y);
95         lastans=b[query(fr[z],fr[f[z][0]],fr[x],fr[y],1,n,k)].x;
96         printf("%d\n",lastans);    
97     }
98 }

 tyvj1728

6个操作

添加数，删除数，查询第k小，查询数的排名，查询前驱，查询后继

权值线段树，注意返回顺序

#include
using namespace std;
const int N=1e5+10;
int tr[N*20],ch[N*20][2],nd;
void ins(int rt,long long l,long long r,int x)
{
    tr[rt]++;
    if (l==r) return;
    long long mid=l+r>>1;
    if (x<=mid)
    {
        if (!ch[rt][0]) ch[rt][0]=++nd;
        ins(ch[rt][0],l,mid,x);
    }else
    {
        if (!ch[rt][1]) ch[rt][1]=++nd;
        ins(ch[rt][1],mid+1,r,x);    
    }
}
void dins(int rt,long long l,long long r,int x)
{
    tr[rt]--;
    if (l==r) return;
    long long mid=l+r>>1;
    if (x<=mid)
    {
        if (!ch[rt][0]) ch[rt][0]=++nd;
        dins(ch[rt][0],l,mid,x);
    }else
    {
        if (!ch[rt][1]) ch[rt][1]=++nd;
        dins(ch[rt][1],mid+1,r,x);    
    }
}
int q3(int rt,long long l,long long r,int x,int y)
{
    if (!rt) return 0;
    if (l>=x&&r<=y) return tr[rt];
    long long mid=l+r>>1,ret=0;
    if (x<=mid) ret=ret+q3(ch[rt][0],l,mid,x,y);
    if (y>mid) ret=ret+q3(ch[rt][1],mid+1,r,x,y);
    return ret; 
}
int q4(int rt,long long l,long long r,int x)
{
    if (l==r) return l;
    long long mid=l+r>>1,tmp=tr[ch[rt][0]];
    if (x<=tmp) return q4(ch[rt][0],l,mid,x);
    return q4(ch[rt][1],mid+1,r,x-tmp);     
}
long long q5(int rt,long long l,long long r,int x,int y)
{

    long long mid=l+r>>1,ret=-2e9-1;
    if (!tr[rt]) return ret;
    if (l==r) return l;
    if (l>=x&&r<=y)
    {
        int tmp=tr[ch[rt][1]];
        if (tmp) return q5(ch[rt][1],mid+1,r,x,y);    
        return q5(ch[rt][0],l,mid,x,y);
    }
    if (x<=mid) ret=max(ret,q5(ch[rt][0],l,mid,x,y));
    if (y>mid) ret=max(ret,q5(ch[rt][1],mid+1,r,x,y));
    return ret;
}
long long q6(int rt,long long l,long long r,int x,int y)
{
    long long mid=l+r>>1,ret=2e9+1;
    if (!tr[rt]) return ret;
    if (l==r) return l;
    if (l>=x&&r<=y)
    {
        int tmp=tr[ch[rt][0]];
        if (tmp) return q6(ch[rt][0],l,mid,x,y);
        return q6(ch[rt][1],mid+1,r,x,y);
    }
    if (x<=mid) ret=min(ret,q6(ch[rt][0],l,mid,x,y));
    if (y>mid) ret=min(ret,q6(ch[rt][1],mid+1,r,x,y));
    return ret;
}
int main()
{
    //freopen("test.in","r",stdin);
    nd=1;
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int tp,x;
        scanf("%d%d",&tp,&x);
        if (tp==1) ins(1,-2e9,2e9,x);else 
        if (tp==2) dins(1,-2e9,2e9,x);else 
        if (tp==3) printf("%d\n",q3(1,-2e9,2e9,-2e9,x-1)+1);else
        if (tp==4) printf("%d\n",q4(1,-2e9,2e9,x));else
        if (tp==5) printf("%d\n",q5(1,-2e9,2e9,-2e9,x-1));else
        if (tp==6) printf("%d\n",q6(1,-2e9,2e9,x+1,2e9));
    }
}