Si_Yue小屋
0%

线段树套二分

发表于 分类于

原题链接

妃爱流汗

本题的题意很容易想清楚是要去寻找左右最大的边界 \(L\)，\(R\)，这样就能用数据结构很好的维护权值的单点修区间和。但是如何去考虑这个边界呢？很容易想到是二分这个边界，但是怎么做到在线去处理这个颜色改变的信息呢？

对每种颜色都建立一个0/1动态开点线段树，存下每个树的根，然后每次跳区间的时候带着这些根一起跳，一起统计区间的和，如果区间的和与区间长度一致，说明依然合法，继续向外寻找边界。这么做的时间复杂度是 \(O((n+q)\log(n)+\sum k\log(n))\) 的，效率很好，不要忘了动态开点的空间是 \(n\log(n)\) 的，记不住不放心就多乘个2的空间。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define int long long
const int N=1e5+10;
const int Q=1e5+10;
const int M=20*(N+Q);

int read(){
    int res=0,sign=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')sign=-sign;
    for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<3)+(res<<1)+(ch^'0');
    return res*sign;
}

int n,q;
int c[N],v[N];

struct bit_t{
    LL d[N];
    void init(){for(int i=1;i<=n;++i)d[i]=0;}
    void modify(LL x,LL c){
        for(;x<=n;x+=x&-x)d[x]+=c;
    }
    LL query(LL x){
        LL res=0;
        for(;x;x-=x&-x)res+=d[x];
        return res; 
    }
}bit;

struct segtree_t{
    int rt[N],cnt;
    struct node_t{
        int v,lson,rson;
    }d[M];
    #define ls d[p].lson
    #define rs d[p].rson
    #define MID int m=s+((t-s)>>1)

    void init(){cnt=0;for(int i=1;i<=n;++i)rt[i]=0;};

    inline void pushup(int p){d[p].v=d[ls].v+d[rs].v;}

    void modify(int& p,int s,int t,int x,int c){
        if(!p)p=++cnt,ls=rs=d[p].v=0;
        if(s==t){
            d[p].v+=c;
            return;
        }
        MID;
        if(x<=m)modify(ls,s,m,x,c);
        else modify(rs,m+1,t,x,c);
        pushup(p);
    }

    int calc(vector<int>& sub){
        int res=0;
        for(auto& p:sub){
            res+=d[p].v;
        }
        return res;
    }

    vector<int> getls(vector<int> sub){
        for(auto& p:sub){
            p=ls;
        }
        return sub;
    }

    vector<int> getrs(vector<int> sub){
        for(auto& p:sub){
            p=rs;
        }
        return sub;
    }

    int findl(vector<int> sub,int s,int t,int x){
        if(calc(sub)==t-s+1)return 0;
        if(s==t)return s;
        MID;
        if(x<=m){
            return findl(getls(sub),s,m,x);
        }else{
            int res=findl(getrs(sub),m+1,t,x);
            return res==0?findl(getls(sub),s,m,x):res;
        }
    }

    int findr(vector<int> sub,int s,int t,int x){
        if(calc(sub)==t-s+1)return n+1;
        if(s==t)return s;
        MID;
        if(x<=m){
            int res=findr(getls(sub),s,m,x);
            return res==n+1?findr(getrs(sub),m+1,t,x):res;
        }else{
            return findr(getrs(sub),m+1,t,x);
        }
    }
}segtree;  

void solve(){
    n=read(),q=read();
    bit.init();
    segtree.init();
    for(int i=1;i<=n;++i){
        c[i]=read();
        segtree.modify(segtree.rt[c[i]],1,n,i,1);
    }
    for(int i=1;i<=n;++i){
        v[i]=read();
        bit.modify(i,v[i]);
    }
    for(int i=1,op;i<=q;++i){
        op=read();
        if(op==1){
            int p=read(),x=read();
            segtree.modify(segtree.rt[c[p]],1,n,p,-1);
            c[p]=x;
            segtree.modify(segtree.rt[c[p]],1,n,p,1);
        }else if(op==2){
            int p=read(),x=read();
            bit.modify(p,x-v[p]);
            v[p]=x;
        }else if(op==3){
            int x=read(),k=read();
            vector<int> colors(k);
            for(auto& cc:colors){
                cc=read();
                cc=segtree.rt[cc];
            }
            int L,R;
            L=segtree.findl(colors,1,n,x);
            R=segtree.findr(colors,1,n,x);
            ++L,--R;
            LL ans=0;
            if(L<=R){
                ans=bit.query(R)-bit.query(L-1);
            }
            printf("%lld\n",ans);
        }
    }
}

signed main(){
    int t=read();
    while(t--)solve();   
}

但是这个题还有一种效率低了很多倍不过可以过的方法，那就是直接每个颜色都开一个平衡树，用平衡树去查询区间中有多少个有该颜色的点，这样子去二分这个边界。这样子做的复杂度是 \(O(n\log(n)+\sum k\log^2(n))\)

,就给每次的 \(k\) 上面多了一个大常数 \(\log(n)\) ，不过时限很大，是可以过的。赛时写平衡树耗时间，用 pbds 过这个题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define int long long

using namespace std;
using namespace __gnu_pbds;

const int N=1e5+10;

int read(){
    int res=0,sign=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')sign=-sign;
    for(;ch>='0'&&ch<='9';ch=getchar())res=(res<<3)+(res<<1)+(ch^'0');
    return res*sign;
}

tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> S[N];

int query(int l,int r,int x){
    return S[x].order_of_key(r+1)-S[x].order_of_key(l);
}

int c[N],v[N];
int n,q;
vector<int> col;

bool check(int l,int r){
    int res=0;
    for(auto&& x:col){
        res+=query(l,r,x);
    }
    return res==r-l+1;
}

struct bit_t{
    int d[N];
    void init(){for(int i=1;i<=n;++i)d[i]=0;}
    void modify(int x,int c){
        for(;x<=n;x+=x&-x)d[x]+=c;
    }
    int query(int x){
        int res=0;
        for(;x;x-=x&-x)res+=d[x];
        return res; 
    }
}bit;

void solve(){
    n=read(),q=read();
    bit.init();
    for(int i=1;i<=n;++i)S[i].clear();
    for(int i=1;i<=n;++i){
        c[i]=read();
        S[c[i]].insert(i);
    }
    for(int i=1;i<=n;++i){
        v[i]=read();
        bit.modify(i,v[i]);
    }
    for(int i=1,op;i<=q;++i){
        op=read();
        if(op==1){
            int p=read(),x=read();
            S[c[p]].erase(p);
            c[p]=x;
            S[c[p]].insert(p);
        }else if(op==2){
            int p=read(),x=read();
            bit.modify(p,x-v[p]);
            v[p]=x;
        }else if(op==3){
            int x=read(),k=read();
            col.clear();
            for(int i=1,tmp;i<=k;++i)col.push_back(tmp=read());
            int L,R;
            int l=1,r=x,mid;
            while(l<=r){
                mid=l+r>>1;
                if(check(mid,x))r=mid-1;
                else l=mid+1;
            }
            L=l;
            l=x,r=n;
            while(l<=r){
                mid=l+r>>1;
                if(check(x,mid))l=mid+1;
                else r=mid-1;
            }
            R=r;
            int ans=bit.query(R)-bit.query(L-1);
            printf("%lld\n",ans);
        }
    }
}

signed main(){
    int t=read();
    while(t--)solve();
}