线段树的一些trick | vegeone

vegeone
0%

线段树的一些trick

发表于 更新于 分类于 Valine：

以下是我根据洛谷limit的线段树题单中挑了一部分有趣的题来做，一些trick还是比较有意思的。

XOR on Segment

https://www.luogu.com.cn/problem/CF242E

思路

维护二进制下各位区间内1的数量，因为当对于一个区间都异或x时，若x对应位为1，则区间内1的数量不变；若对应位为0，则区间内1的数量为区间长度-区间内1的数量（即取反），区间和即为各位1的数量并转为十进制。

1
2
3
4
5
6
7
void settag(int id,tag t){
	node[id].t=node[id].t+t;
	for(int i=0;i<=20;++i){
        int tt=(t.opt)>>i&1;
        node[id].val.cnt[i]=(tt?node[id].sz-node[id].val.cnt[i]:node[id].val.cnt[i]);
    }
}

New Year Tree

https://www.luogu.com.cn/problem/CF620E

思路

注意到颜色只有60种，可以通过bitset来存储颜色，树剖实现整体框架

1
2
3
4
5
void settag(int id,int t){
    node[id].tag=t;
    node[id].val.bt.reset();
    node[id].val.bt.set(t);
}

The Child and Sequence

https://www.luogu.com.cn/problem/CF438D

区间取模

思路

暴力修改到结点，同时维护区间最大值，若最大值小于模数则停止递归

1
if(node[id].val.maxn<d)return;

引申

区间求开方

1
if(node[id].val.sum==node[id].sz)return;

TorCoder

https://www.luogu.com.cn/problem/CF240F

给定一个长为的由a到z组成的字符串,有次操作，每次操作将这些位置的字符进行重排，得到字典序最小的回文字符串，如果无法操作就不进行。
求次操作后的字符串。

思路

维护区间各字母的数量，暴力安排每一步操作
容易卡常QAQ

Nastya and King-Shamans

https://www.luogu.com.cn/problem/CF992E

给定一个序列 ，记其前缀和序列为 ，有 个询问，每次单点修改，询问是否存在一个 满足 ，有多解输出任意一个，无解输出 −1 。

One Occurrence

https://www.luogu.com.cn/problem/CF1000F

给定一个长度为序列,个询问，每次询问给定一个区间，如果这个区间里存在只出现一次的数，输出这个数（如果有多个就输出任意一个），没有就输出0，

思路

从左往右扫，val存储对应位置之前出现的位置中最靠前的值以及对应的数。

Boring Queries

https://www.luogu.com.cn/problem/CF1422F

在线求给定区间的lcm

思路

对于区间右端点固定，当左端点向左移动时，每次会增加一个数。当且仅当增加的数存在一个因子 ，原来的lcm的p的指数小于w时，答案会增大。更具体一点，原来lcm的p的指数会对w取max。

这样对于两个数，质因子p对应的指数分别为x,y，若x<y，则一定不会更新答案。这样的可以直接丢掉。

代码

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
#include<bits/stdc++.h>
// #define int long long
using namespace std;
#define endl '\n'
typedef pair<int,int>pp;
typedef long long LL;
const int P = 1e9+7;
LL n,q,idx;
const int N=1e5+10,M=2e5+10;
int a[N],root[N];
struct info{
    LL sum;
};
struct Node{
    int l,r;
    info val;
}node[N*200];
info operator+(const info &a,const info &b){
    return {a.sum*b.sum%P};
}
int build(int l,int r){
    int p=++idx;
    node[p].val.sum=1;
    if(l==r)return r;
    int mid=(l+r)>>1;
    node[p].l=build(l,mid);
    node[p].r=build(mid+1,r);
    return p;
}
void update(int p){
    node[p].val=node[node[p].l].val+node[node[p].r].val;
}
int insert(int p,int l,int r,int x,int d){
    int q=++idx;
    node[q]=node[p];
    if(l==r){
        node[q].val.sum=(node[q].val.sum*d)%P;
        return q;
    }
    int mid=(l+r)>>1;
    if(x<=mid)node[q].l=insert(node[q].l,l,mid,x,d);
    else node[q].r=insert(node[q].r,mid+1,r,x,d);
    update(q);
    return q;
}
info query(int p,int l,int r,int ql,int qr){
    if(l==ql&&r==qr)return node[p].val;
    int mid=(l+r)>>1;
    if(qr<=mid)return query(node[p].l,l,mid,ql,qr);
    else if(ql>mid)return query(node[p].r,mid+1,r,ql,qr);
    else return query(node[p].l,l,mid,ql,mid)+query(node[p].r,mid+1,r,mid+1,qr);    
}
int b[M],pre[M];
LL qmi(LL a,LL b){
    LL res=1;
    a%=P;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P;
        b>>=1;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=2;i<=200000;++i){
        if(!b[i]){
            for(int j=1;i*j<=200000;++j){
                b[i*j]=i;
            }
        }
    }
    for(int i=1;i<=n;++i)cin>>a[i];
    root[0]=build(1,n);
    vector<pp>vec;
    for(int i=1;i<=n;++i){
        vec.clear();
        int x=a[i];
        root[i]=root[i-1];
        while(b[x]){
            int d=b[x],cnt=0,k=1;
            int inv=qmi(d,P-2);
            while(x%d==0){
                x/=d;
                ++cnt;
                k*=d;
                if(pre[k])vec.push_back({pre[k],inv});
                pre[k]=i;
            }
            pre[k]=i;
            root[i]=insert(root[i],1,n,i,k);
        }
        if(x){
            if(pre[x])vec.push_back({pre[x],qmi(x,P-2)});
            pre[x]=i;
            root[i]=insert(root[i],1,n,i,x);
        }
        LL res=0;
        for(int j=0;j<vec.size();++j){
            if(!j||vec[j].first!=vec[j-1].first)res=1;
            res=res %P *vec[j].second % P;
            if(j+1==vec.size()||vec[j].first!=vec[j+1].first)root[i]=insert(root[i],1,n,vec[j].first,res);
            //cerr<<i<<" "<<j<<" "<<vec[j].first<<" "<<vec[j].second<<" "<<res<<endl;
        }
    }
    cin>>q;
    int ans=0;
    while(q--){
        int l,r;
        cin>>l>>r;
        //int temp=(int)ans;
        l=(l+ans)%n+1,r=(r+ans)%n+1;
        //cerr<<l<<" "<<r<<endl;
        if(l>r)swap(l,r);
        ans=query(root[r],1,n,l,r).sum;
        cout<<ans<<endl;
    }
    
    return 0;
}