我们假设询问区间为整个区间
[
1
,
N
]
[1,N]
[1,N], 该怎么做？ 我们可以把序列升序排序，然后一个一个访问过去 我们现在访问到第
i
i
i 个数字
A
i
A_i
Ai 假设我们现在能表示出
[
0
,
x
]
[0,x]
[0,x] 的值，如果
A
i
>
x
+
1
A_i>x+1
Ai>x+1，那么我们之后都无法表示出
x
+
1
x+1
x+1了，答案就是
x
+
1
x+1
x+1 否则，我们加上这个数字，则能表示出
[
0
,
x
+
A
i
]
[0,x+A_i]
[0,x+Ai] 中的值，继续下一个遍历即可
我们现在考虑询问区间为
[
L
,
R
]
[L,R]
[L,R], 该怎么做？ 假设我们现在能表示出
[
0
,
x
]
[0,x]
[0,x] 的值，且我们已经用过区间中所有
A
i
≤
l
a
s
t
A_i\le last
Ai≤last 的值 那么，我们需要查询值域为
[
l
a
s
t
+
1
,
x
+
1
]
[last+1,x+1]
[last+1,x+1] 中，下标为
[
L
,
R
]
[L,R]
[L,R] 中是否有某个数字
y
y
y 如果有，则我们能表示出
[
0
,
x
+
y
]
[0,x+y]
[0,x+y] 的值
换句话说，我们需要查询值域为
[
l
a
s
t
+
1
,
x
+
1
]
[last+1,x+1]
[last+1,x+1] 中，下标为
[
L
,
R
]
[L,R]
[L,R] 中所有的数字总和
s
u
m
sum
sum 如果有，则我们能表示出
[
0
,
x
+
s
u
m
]
[0,x+sum]
[0,x+sum] 的值 然后我们更新一下，
l
a
s
t
last
last 变成了
x
+
1
x+1
x+1，
x
x
x 变成了
x
+
s
u
m
x+sum
x+sum 如果没有，则我们答案为
x
+
1
x+1
x+1
接下来，我们的唯一要求就是怎么求出 下标
[
L
,
R
]
[L,R]
[L,R] 范围之内，值域
[
x
,
y
]
[x,y]
[x,y] 范围之内的数字和 考虑主席树，我们每个点设一个子树数字和
s
u
m
sum
sum 那么我们下标范围之内的子树数字和就是
r
o
o
t
[
R
]
.
s
u
m
−
r
o
o
t
[
L
−
1
]
.
s
u
m
root[R].sum-root[L-1].sum
root[R].sum−root[L−1].sum 然后就和一般的主席树更新一样了
我这里不知道为什么
T
L
E
\color{red}TLE
TLE 了，我加了一个剪枝优化： if(tree[c2].sum - tree[c1].sum == 0) return 0; 如果目前我们满足要求的子树数字和为
0
0
0 ，那就不用找了，直接返回即可 时间从
>
4000
M
s
>4000Ms
>4000Ms 优化到
1500
M
s
1500Ms
1500Ms
代码
时间复杂度：
O
(
n
log
X
+
Q
log
2
X
)
O(n\log X+Q\log^2 X)
O(nlogX+Qlog2X)，其中
X
>
1
0
9
X>10^9
X>109 就是数字的上限
#include<bits/stdc++.h>
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x << " ] , ";show(args...);}
#define ll long long
#define ls tree[p].lson
#define rs tree[p].rson
#define md ((l+r)>>1)
const int MAX = 1e6+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;
int aa[MAX];
struct SegmentTree{
int lson,rson;
ll sum;
}tree[MAX*40];
int root[MAX];
int idx;
void NewNode(){
idx++;
tree[idx].lson = tree[idx].rson = tree[idx].sum = 0;
}
void push_up(int p){
tree[p].sum = tree[ls].sum + tree[rs].sum;
}
void Insert(int p,int l,int r,ll k){
tree[p].sum += k;
if(l == r)return;
NewNode();
if(k <= md){
if(ls)tree[idx] = tree[ls];
ls = idx;
Insert(ls,l,md,k);
}else{
if(rs)tree[idx] = tree[rs];
rs = idx;
Insert(rs,md+1,r,k);
}
push_up(p);
}
ll query(int l,int r,const ll &qx,const ll &qy,int c1,int c2){ // 注意询问范围是 long long 的！
if(tree[c2].sum - tree[c1].sum == 0)return 0;
if(qx <= l && qy >= r){
return tree[c2].sum - tree[c1].sum;
}
ll res = 0;
if(md >= qx)res += query(l,md,qx,qy,tree[c1].lson,tree[c2].lson);
if(md < qy)res += query(md+1,r,qx,qy,tree[c1].rson,tree[c2].rson);
return res;
}
const int YOU = 1000000000;
int n,m;
void init(){
idx = 0;
n = read();m = read();
for(int i = 1;i <= n;++i){
aa[i] = read();
}
NewNode();
root[0] = idx;
for(int i = 1;i <= n;++i){
NewNode();
root[i] = idx;
tree[root[i]] = tree[root[i-1]];
Insert(root[i],1,YOU,aa[i]);
}
}
int main()
{
init();
ll lst = 0,you = 0;
for(int i = 1;i <= m;++i){
int l1,r1,l,r;
l1 = read();r1 = read();
l = min( (l1+you) % n + 1,(r1 + you) % n + 1);
r = max( (l1+you) % n + 1,(r1 + you) % n + 1);
lst = you = 0;
while(1){
ll sum = query(1,YOU,lst+1,you+1,root[l-1],root[r]);
// show(l,r,lst+1,you+1,sum);
if(sum == 0)break;
lst = you + 1;
you = you + sum;
}
you++;
Print(you,'\n');
}
Write();
return 0;
}