Static Query on Tree（树链剖分）

问题可以转化为求三个集合的交集

const int N=2e5+10,M=2*N;
int n,q;
int h[N],e[M],ne[M],idx;
int fa[N],siz[N],son[N],dep[N];
int id[N],rid[N],top[N],num;
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int f){
    son[u]=0;
    fa[u]=f;siz[u]=1;
    dep[u]=dep[f]+1;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==f) continue;
        dfs1(j,u);
        siz[u]+=siz[j];
        if(!son[u]||siz[j]>siz[son[u]]) son[u]=j;
    }
}
void dfs2(int u,int t){
    id[u]=++num,rid[num]=u,top[u]=t;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa[u]||j==son[u]) continue;
        dfs2(j,j);
    }
}
void join(int a,int b,vector<PII>&ve){//点加入集合
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]]) swap(a,b);
        ve.push_back({id[top[a]],id[a]});
        a=fa[top[a]];
    }
    if(dep[a]<dep[b]) swap(a,b);
    ve.push_back({id[b],id[a]});
}
void merge(vector<PII>&ve){//合并集合内重复区间
    if(!ve.size()) return ;
    vector<PII>t;
    sort(ve.begin(),ve.end());
    int st=ve[0].l,ed=ve[0].r;
    for(auto i:ve){
        if(i.l>ed){
            t.push_back({st,ed});
            st=i.l,ed=i.r;
        }
        else ed=max(ed,i.r);
    }
    t.push_back({st,ed});
    ve=t;
}
vector<PII> intersection(vector<PII>a,vector<PII>b){//集合合并
    vector<PII>ve;
    int i=0,j=0;
    while(i<a.size()&&j<b.size()){
        int l=max(a[i].l,b[j].l);
        int r=min(a[i].r,b[j].r);
        if(l<=r) ve.push_back({l,r});
        if(a[i].r<b[j].r) i++;
        else j++;
    }
    return ve;
}
void solve(){
    cin>>n>>q;

    idx=num=0;
    for(int i=1;i<=n;i++) h[i]=-1;

    for(int i=2;i<=n;i++){
        int x; cin>>x;
        add(x,i),add(i,x);
    }
    dfs1(1,0);dfs2(1,1);
    while(q--){
        vector<PII>a,b,c;
        int x,y,z,u;cin>>x>>y>>z;
        while(x--){
            cin>>u;
            join(1,u,a);
        }
        while(y--){
            cin>>u;
            join(1,u,b);
        }
        while(z--){
            cin>>u;
            c.push_back({id[u],id[u]+siz[u]-1});
        }
        merge(a);merge(b),merge(c);
        a=intersection(a,b);
        a=intersection(a,c);
        int res=0;
        for(auto i:a){
            res+=i.r-i.l+1;
        }
        cout<<res<<endl;
    }
}
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

Copy（离线+bitset优化）

离线操作，正向枚举询问不容易做，考虑反向枚举

每次是使[l,r]插入到r的后面，

当选择的位置x<=r时反向正向没有区别，

当x>r时，需要将反向查询的位置向左偏移r-l+1（向下标小的位置偏移）

题目求得时异或值，只需要记录是否出现过奇数次，所以可以用bitset判断每个位置的出现次数，并实现O(1)修改偏移量

const int N=1e5+10;
int n,m;
int g[N],q[N][3];
bitset<N>f,low,high;
inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>g[i];
    for(int i=0;i<m;i++){
        cin>>q[i][0]>>q[i][1];
        if(q[i][0]==1) cin>>q[i][2];
    }
    f.reset();
    for(int i=m-1;i>=0;i--){
        if(q[i][0]==1){
            int l=q[i][1],r=q[i][2];
            //将f分为[1,r],[r+1,n]两部分
        
            low=f&(~bitset<N>(0)>>(N-(r+1)));//前r+1位，因为第一位下标为0
            high=f&(~bitset<N>(0)<<(r+1));//r+1~n
            f=low^(high>>(r-l+1));
        }
        else{
            int x=q[i][1];
            f[x]=!f[x];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(f[i]) ans^=g[i];
    }
    cout<<ans<<endl;
}
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

DOS Card（线段树+暴力）

巧妙的做法

把所有情况表示出来：

求++--或则+-+-的最大值

维护出所有能更新成上述两种情况的max

+ -
++ --
+- -+
++- +--
+-+ -+-
1
2
3
4
5

const int N=2e5+10;
int n,m,g[N];
struct P{
    int l,r;
    int res1,res2;//++-- +-+-
    int a,b;//+ -
    int c,d;//++ --
    int e,f;//+- -+
    int g,h;//++- +--
    int i,j;//+-+ -+-
    void init(int ll,int rr){
        l=ll,r=rr;
        res1=res2=a=b=c=d=e=f=g=h=i=j=-INF;
    }
}tr[4*N];
void pushup(P &u,P l,P r){
    u.res1=max(l.res1,r.res1);
    u.res2=max(l.res2,r.res2);
    u.a=max(l.a,r.a);
    u.b=max(l.b,r.b);
    u.c=max(l.c,r.c);
    u.d=max(l.d,r.d);
    u.e=max(l.e,r.e);
    u.f=max(l.f,r.f);
    u.g=max(l.g,r.g);
    u.h=max(l.h,r.h);
    u.i=max(l.i,r.i);
    u.j=max(l.j,r.j);

    u.res1=max(u.res1,l.a+r.h);
    u.res1=max(u.res1,l.c+r.d);
    u.res1=max(u.res1,l.g+r.b);
    u.res2=max(u.res2,l.e+r.e);
    u.res2=max(u.res2,l.a+r.j);
    u.res2=max(u.res2,l.i+r.b);

    u.c=max(u.c,l.a+r.a);
    u.d=max(u.d,l.b+r.b);
    u.e=max(u.e,l.a+r.b);
    u.f=max(u.f,l.b+r.a);
    u.g=max(u.g,l.c+r.b);
    u.g=max(u.g,l.a+r.e);
    u.h=max(u.h,l.a+r.d);
    u.h=max(u.h,l.e+r.b);
    u.i=max(u.i,l.e+r.a);
    u.i=max(u.i,l.a+r.f);
    u.j=max(u.j,l.b+r.e);
    u.j=max(u.j,l.f+r.b);
}
void pushup(int u){
    pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
    tr[u].init(l,r);
    if(l==r) tr[u].a=g[l],tr[u].b=-g[l];
    else{
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
P query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
    int mid=tr[u].l+tr[u].r>>1;
    if(r<=mid) return query(u<<1,l,r);
    if(l>mid) return query(u<<1|1,l,r);
    P root;
    root.init(0,0);
    pushup(root,query(u<<1,l,r),query(u<<1|1,l,r));
    return root;
}
inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>g[i],g[i]*=g[i];
    build(1,1,n);
    while(m--){
        int l,r; cin>>l>>r;
        P u=query(1,l,r);
        cout<<max(u.res1,u.res2)<<endl;
    }
}
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

Slayers Come（线段树维护dp+并查集+双指针）

先预处理出选择每个技能对应能杀死的怪物的区间

处理后问题转换为在m个技能中选择可以将整个区间覆盖（每个点可覆盖任意多次）的方案数

dp[i]表示将区间[1,i]覆盖的方案数
对于每个区间[l,r]
dp[r]+=dp[l-1~r](l-1到r的方案数)
因为先前更新的dp未考虑当前区间
所以
dp[1~l-2]*=2(1到l-2未考虑当前区间)

对一个区间乘，单点加，区间查询可以使用线段树
1
2
3
4
5
6
7
8

如果处理出区间？

对于右端点

$a[i]-r[j]>=b[i+1]\Rightarrow a[i]-b[i+1]>=r[j]$

设$s[i]=a[i]-b[i+1]$，对s递增排序，对r递减排序

若当前$s[i]>r[j]$，说明选择技能j可以杀死怪物i（需要求出对应的排序前的位置）

因为r递减，所以后面的技能一定满足杀死当前怪物（双指针）

只需找出来每个怪物之间是否来连通，用并查集维护每个怪物之间的关系

左端点同理

const int N=1e5+10;
int n,m;
int a[N],b[N],f[N];
PII s[N];
struct P{
    int l,r,v;
    int ll,rr;
}g[N];
struct Node{
    int l,r;
    int sum;
    int lazy;
}tr[4*N];
int find(int x){
    return f[x]==x?f[x]:f[x]=find(f[x]);
}
void pushdown(int u){
    Node &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.lazy!=1){
        left.sum=left.sum*root.lazy%mod;
        right.sum=right.sum*root.lazy%mod;
        left.lazy=left.lazy*root.lazy%mod;
        right.lazy=right.lazy*root.lazy%mod;
        root.lazy=1;
    }
}
void pushup(int u){
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%mod;
}
void build(int u,int l,int r){
    tr[u]={l,r,0,1};
    if(l!=r){
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void add(int u,int x,int v){
    if(tr[u].l==x&&tr[u].r==x){
        tr[u].sum=(tr[u].sum+v)%mod;
        return ;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid) add(u<<1,x,v);
    else add(u<<1|1,x,v);
    pushup(u);
}
void mul(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].sum=tr[u].sum*2%mod;
        tr[u].lazy=tr[u].lazy*2%mod;
        return ;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) mul(u<<1,l,r);
    if(r>mid) mul(u<<1|1,l,r);
    pushup(u);
}
int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    int res=0;
    if(l<=mid) res+=query(u<<1,l,r);
    if(r>mid) res+=query(u<<1|1,l,r);
    res%=mod;
    return res;
}
inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=m;i++){
        int l,r,v; cin>>v>>l>>r;
        g[i]={l,r,v};
    }

    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<n;i++) s[i]={a[i]-b[i+1],i};
    sort(s+1,s+n);
    sort(g+1,g+1+m,[](P &x,P &y){
        return x.r>y.r;
    });
    for(int i=1,j=n-1;i<=m;i++){
        while(j>=1&&s[j].x>=g[i].r){
            int pos=s[j].y;
            f[pos]=pos+1;
            j--;
        }
        g[i].rr=find(g[i].v);
    }

    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<n;i++) s[i]={a[i+1]-b[i],i};
    sort(s+1,s+n);
    sort(g+1,g+1+m,[](P &x,P &y){
         return x.l>y.l;
    });
    for(int i=1,j=n-1;i<=m;i++){
        while(j>=1&&s[j].x>=g[i].l){
            int pos=s[j].y;
            f[pos+1]=pos;
            j--;
        }
        g[i].ll=find(g[i].v);
    }
    sort(g+1,g+1+m,[](P &x,P &y){
        return x.rr<y.rr;
    });
    //单点加，区间乘，区间和查询
    build(1,0,n);
    add(1,0,1);
    for(int i=1;i<=m;i++){
        int l=g[i].ll,r=g[i].rr;
       // cout<
        add(1,r,query(1,l-1,r));
        if(l>=2) mul(1,0,l-2);
    }
    cout<<query(1,n,n)<<endl;
}
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