推荐几篇好的博客
以及这个题单
普通莫队
莫队算法是一种基于分块思想的离线算法
可以用来维护区间的答案和区间的数据结构
首先我们把长度为 (n) 的序列划分为 (sqrt{n}) 个长度为 (sqrt{n}) 的块并标号
然后把所有的询问离线下来，按照左端点所在的块的标号排序，如果标号相同，则按照右端点从小到大排序
询问的时候维护一个区间最左端的指针和一个区间最右端的指针
每次处理一个新的询问时，就分别移动左指针和右指针，使它们分别与新的询问的左右端点重合并记录答案
最后把存到数组里的答案输出即可
一般来说，(n) 和 (m) 可以看做是相等的，所以块长取 (sqrt{n}) 最优
对于右端点来说，每一个块内的右端点是单调的，最多移动 (n) 的长度，一共有 (sqrt{n}) 个块，所以复杂度为 (nsqrt{n})
对于左端点来说，每次最多移动一个块长，一共有 (n) 个左端点，所以复杂度为 (nsqrt{n})
再加上排序的 (nlogn) ,总的时间复杂度就是 (nsqrt{n})
但是当 (n) 和 (m) 不相等的时候，块长取 (frac{n}{sqrt{m}}) 是最优的，此时时间复杂度为 (nsqrt{m})
使用莫队算法的前提是没有强制在线，并且每次移动左指针和右指针改变的贡献能够快速计算
莫队算法在排序的时候还有一个奇偶性优化
如果左端点所属的联通块标号为奇数，按照右端点从小到大排序
否则按照右端点从大到小排序
这样排序大约要快 (30\%) 左右
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int shuyu[maxn],a[maxn],n,m,k,cnt[maxn],num,blo,ans[maxn];
struct asd{
int jla,jlb,id;
}b[maxn];
bool cmp(asd aa,asd bb){
if(shuyu[aa.jla]==shuyu[bb.jla]) return shuyu[aa.jla]&1?aa.jlb<bb.jlb:aa.jlb>bb.jlb;
return aa.jla<bb.jla;
}
void xg(rg int now,rg int jud){
num-=cnt[now]*cnt[now];
cnt[now]+=jud;
num+=cnt[now]*cnt[now];
}
int main(){
n=read(),m=read(),k=read();
blo=sqrt(n);
for(rg int i=1;i<=n;i++){
a[i]=read();
shuyu[i]=(i-1)/blo+1;
}
for(rg int i=1;i<=m;i++){
b[i].jla=read(),b[i].jlb=read(),b[i].id=i;
}
std::sort(b+1,b+1+m,cmp);
rg int l=1,r=0;
for(rg int i=1;i<=m;i++){
while(r<b[i].jlb) xg(a[++r],1);
while(l>b[i].jla) xg(a[--l],1);
while(r>b[i].jlb) xg(a[r--],-1);
while(l<b[i].jla) xg(a[l++],-1);
ans[b[i].id]=num;
}
for(rg int i=1;i<=m;i++) printf("%d
",ans[i]);
return 0;
}
二维莫队
莫队也可以处理二维平面上的问题
但是排序的方式要改变一下
第一关键字：左上角的点的横坐标
第二关键字：左上角的点的纵坐标
第三关键字：右下角的点的横坐标
第四关键字：右下角的点的纵坐标
复杂度 (n^2m^{frac{3}{4}})
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=205,maxm=1e6+5;
int n,m,q,a[maxn][maxn],shuyu[maxn],blo,ans[maxm],nans,sta[maxm],top,cnt[maxm];
struct asd{
int ax,ay,bx,by,id;
asd(){}
asd(int aa,int bb,int cc,int dd,int ee){
ax=aa,ay=bb,bx=cc,by=dd,id=ee;
}
}b[maxm];
bool cmp(asd aa,asd bb){
if(shuyu[aa.ax]==shuyu[bb.ax]){
if(shuyu[aa.ay]==shuyu[bb.ay]){
if(shuyu[aa.bx]==shuyu[bb.bx]) return shuyu[aa.by]<shuyu[bb.by];
else return shuyu[aa.bx]<shuyu[bb.bx];
} else {
return shuyu[aa.ay]<shuyu[bb.ay];
}
} else {
return shuyu[aa.ax]<shuyu[bb.ax];
}
}
void xgh(int aa,int bb,int hs,int op){
for(rg int i=aa;i<=bb;i++){
nans-=cnt[a[hs][i]]*cnt[a[hs][i]];
cnt[a[hs][i]]+=op;
nans+=cnt[a[hs][i]]*cnt[a[hs][i]];
}
}
void xgl(int aa,int bb,int ls,int op){
for(rg int i=aa;i<=bb;i++){
nans-=cnt[a[i][ls]]*cnt[a[i][ls]];
cnt[a[i][ls]]+=op;
nans+=cnt[a[i][ls]]*cnt[a[i][ls]];
}
}
int main(){
n=read(),m=read();
blo=sqrt(std::max(n,m))/2*3;
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=m;j++){
a[i][j]=read();
sta[++top]=a[i][j];
}
}
std::sort(sta+1,sta+1+top);
rg int haha=std::unique(sta+1,sta+1+top)-sta-1;
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=m;j++){
a[i][j]=std::lower_bound(sta+1,sta+1+haha,a[i][j])-sta;
}
}
q=read();
rg int aa,bb,cc,dd;
for(rg int i=1;i<=q;i++){
aa=read(),bb=read(),cc=read(),dd=read();
if(aa>cc) std::swap(aa,cc);
if(bb>dd) std::swap(bb,dd);
b[i]=asd(aa,bb,cc,dd,i);
}
for(rg int i=1;i<=std::max(n,m);i++){
shuyu[i]=(i-1)/blo+1;
}
std::sort(b+1,b+1+q,cmp);
rg int nx=1,ny=1,mx=1,my=1;
nans=1;
cnt[a[1][1]]=1;
for(rg int i=1;i<=q;i++){
while(mx<b[i].bx){
mx++;
xgh(ny,my,mx,1);
}
while(my<b[i].by){
my++;
xgl(nx,mx,my,1);
}
while(nx>b[i].ax){
nx--;
xgh(ny,my,nx,1);
}
while(ny>b[i].ay){
ny--;
xgl(nx,mx,ny,1);
}
while(mx>b[i].bx){
xgh(ny,my,mx,-1);
mx--;
}
while(my>b[i].by){
xgl(nx,mx,my,-1);
my--;
}
while(nx<b[i].ax){
xgh(ny,my,nx,-1);
nx++;
}
while(ny<b[i].ay){
xgl(nx,mx,ny,-1);
ny++;
}
ans[b[i].id]=nans;
}
for(rg int i=1;i<=q;i++){
printf("%d
",ans[i]);
}
return 0;
}
带修莫队
普通莫队加上了修改操作
那么排序的时候也要把修改的时间作为一个关键字排序
第一关键字：左端点属于的块
第二关键字：右端点属于的块
第三关键字：到当前查询的时候已经进行了多少次修改操作
当块长为 (n^{frac{2}{3}}) 时，复杂度为 (n^frac{5}{3})
代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5,mod=1e6+3;
int n,a[maxn],q,shuyu[maxn],cnt[maxn],mp[maxn],blo,ans[maxn],nans,sta[maxn],tp,cnt1,cnt2,jl[maxn];
struct jie{
int l,r,id,tim;
jie(){}
jie(rg int aa,rg int bb,rg int cc,rg int dd){
l=aa,r=bb,id=cc,tim=dd;
}
}b[maxn];
bool cmp(jie aa,jie bb){
if(shuyu[aa.l]==shuyu[bb.l] && shuyu[aa.r]==shuyu[bb.r]){
return shuyu[aa.r]&1?aa.tim<bb.tim:aa.tim>bb.tim;
} else if(shuyu[aa.l]==shuyu[bb.l]){
return shuyu[aa.l]&1?aa.r<bb.r:aa.r>bb.r;
} else {
return shuyu[aa.l]<shuyu[bb.l];
}
}
void ad(rg int val){
mp[cnt[val]]--;
cnt[val]++;
mp[cnt[val]]++;
}
void sc(rg int val){
mp[cnt[val]]--;
cnt[val]--;
mp[cnt[val]]++;
}
struct asd{
int wz,bef,lat;
asd(){}
asd(rg int aa,rg int bb,rg int cc){
wz=aa,bef=bb,lat=cc;
}
}c[maxn];
int main(){
n=read(),q=read();
blo=pow(n,2.0/3.0);
for(rg int i=1;i<=n;i++){
jl[i]=a[i]=read();
sta[++tp]=a[i];
shuyu[i]=(i-1)/blo+1;
}
rg int aa,bb,cc;
for(rg int i=1;i<=q;i++){
aa=read(),bb=read(),cc=read();
if(aa==1){
cnt1++;
b[cnt1]=jie(bb,cc,cnt1,cnt2);
} else {
cnt2++;
c[cnt2]=asd(bb,jl[bb],cc);
sta[++tp]=cc;
jl[bb]=cc;
}
}
std::sort(sta+1,sta+1+tp);
tp=std::unique(sta+1,sta+1+tp)-sta-1;
for(rg int i=1;i<=n;i++) a[i]=std::lower_bound(sta+1,sta+1+tp,a[i])-sta;
for(rg int i=1;i<=cnt2;i++){
c[i].bef=std::lower_bound(sta+1,sta+1+tp,c[i].bef)-sta;
c[i].lat=std::lower_bound(sta+1,sta+1+tp,c[i].lat)-sta;
}
std::sort(b+1,b+1+cnt1,cmp);
rg int nl=1,nr=0,ntim=0;
for(rg int i=1;i<=cnt1;i++){
while(ntim<b[i].tim){
ntim++;
if(c[ntim].wz>=nl && c[ntim].wz<=nr){
sc(c[ntim].bef);
ad(c[ntim].lat);
}
a[c[ntim].wz]=c[ntim].lat;
}
while(ntim>b[i].tim){
if(c[ntim].wz>=nl && c[ntim].wz<=nr){
ad(c[ntim].bef);
sc(c[ntim].lat);
}
a[c[ntim].wz]=c[ntim].bef;
ntim--;
}
while(nr<b[i].r){
nr++;
ad(a[nr]);
}
while(nl>b[i].l){
nl--;
ad(a[nl]);
}
while(nr>b[i].r){
sc(a[nr]);
nr--;
}
while(nl<b[i].l){
sc(a[nl]);
nl++;
}
nans=1;
while(mp[nans]) nans++;
ans[b[i].id]=nans;
}
for(rg int i=1;i<=cnt1;i++) printf("%d
",ans[i]);
return 0;
}
回滚莫队
有些情况下，添加值很好做，但是删除值不好做
还有些情况下，删除值很好做，但是添加值不好做
此时普通的莫队无法做到移动左右指针的时候单次 (O(1)) 更新答案
就要用到另一种莫队：回滚莫队
回滚莫队又分为两种：只加不减的和只减不加的
只加不减
这道题要维护最大值
区间伸长的时候很好说，直接和当前的答案取个 (max) 即可
但是区间收缩的时候我们却无法快速地找到次大值，即使我们记录了次大值，有可能下一次又把次大值删除
所以我们要让莫队只能加入贡献，不能删除贡献
首先，我们把询问按照莫队的顺序排序
注意排序时不能使用奇偶性优化，而要按照右端点递增来排
排完序后，询问被分成了 (sqrt{n}) 段
我们把每一段拿出来单独处理
设 (r[i]) 为第 (i) 段的右端点的下标，(l[i])为第 (i) 段的左端点的下标
一开始，我们把左指针设为 (r[i]+1)
把右指针设为 (r[i])
因为在每一段内右端点都是单调递增的，所以右端点一定只有加入的贡献
对于左端点，为了强制只能加入值
我们要在每次操作使用完成后把它回复成 (r[i]+1) 的状态 ，同时把之前左端点做的贡献清除
每一段统计完答案后，我们还要把右端点的贡献清清除
对于长度小于 (sqrt{n}) 的块，暴力统计即可
代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int n,a[maxn],q,shuyu[maxn],cnt[maxn],blo,sta[maxn],tp,lmax[maxn],rmax[maxn],cnt2[maxn];
long long ans[maxn],nans;
struct jie{
int l,r,id;
jie(){}
jie(rg int aa,rg int bb,rg int cc){
l=aa,r=bb,id=cc;
}
}b[maxn];
bool cmp(jie aa,jie bb){
if(shuyu[aa.l]==shuyu[bb.l]){
return aa.r<bb.r;
} else {
return shuyu[aa.l]<shuyu[bb.l];
}
}
void ad(rg int val){
cnt[val]++;
nans=std::max(nans,1LL*sta[val]*cnt[val]);
}
long long solve(rg int l,rg int r){
rg long long mans=0;
for(rg int i=l;i<=r;i++) cnt2[a[i]]++;
for(rg int i=l;i<=r;i++){
mans=std::max(mans,1LL*sta[a[i]]*cnt2[a[i]]);
}
for(rg int i=l;i<=r;i++) cnt2[a[i]]--;
return mans;
}
int main(){
memset(lmax,0x3f,sizeof(lmax));
n=read(),q=read();
blo=sqrt(n);
for(rg int i=1;i<=n;i++){
a[i]=read();
sta[++tp]=a[i];
shuyu[i]=(i-1)/blo+1;
}
std::sort(sta+1,sta+1+tp);
tp=std::unique(sta+1,sta+1+tp)-sta-1;
for(rg int i=1;i<=n;i++) a[i]=std::lower_bound(sta+1,sta+1+tp,a[i])-sta;
for(rg int i=1;i<=n;i++){
rmax[shuyu[i]]=std::max(rmax[shuyu[i]],i);
lmax[shuyu[i]]=std::min(lmax[shuyu[i]],i);
}
for(rg int i=1;i<=q;i++){
b[i].l=read(),b[i].r=read(),b[i].id=i;
}
std::sort(b+1,b+1+q,cmp);
rg int nl=1,nr=0,now=1;
rg long long tmp;
for(rg int i=1;i<=shuyu[n];i++){
memset(cnt,0,sizeof(cnt));
nr=rmax[i];
nans=0;
while(shuyu[b[now].l]==i){
nl=rmax[i]+1;
if(b[now].r-b[now].l<=blo){
ans[b[now].id]=solve(b[now].l,b[now].r);
now++;
continue;
}
while(nr<b[now].r) ad(a[++nr]);
tmp=nans;
while(nl>b[now].l) ad(a[--nl]);
ans[b[now].id]=nans;
nans=tmp;
while(nl<=rmax[i]) cnt[a[nl++]]--;
now++;
}
}
for(rg int i=1;i<=q;i++) printf("%lld
",ans[i]);
return 0;
}
只减不加
和只加不减的莫队同理
只要把右端点改成单调递减
把一开始的右指针置为 (n)，左指针置为 (l[i]) 即可
代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e5+5;
int n,a[maxn],q,shuyu[maxn],cnt[maxn],blo,lmax[maxn],rmax[maxn],cnt2[maxn],ans[maxn],nans,cnt3[maxn];
struct jie{
int l,r,id;
jie(){}
jie(rg int aa,rg int bb,rg int cc){
l=aa,r=bb,id=cc;
}
}b[maxn];
bool cmp(jie aa,jie bb){
if(shuyu[aa.l]==shuyu[bb.l]){
return aa.r>bb.r;
} else {
return shuyu[aa.l]<shuyu[bb.l];
}
}
void sc(rg int val){
cnt[val]--;
if(cnt[val]==0) nans=std::min(nans,val);
}
int solve(rg int l,rg int r){
rg int mans=0;
for(rg int i=l;i<=r;i++){
cnt2[a[i]]++;
}
while(cnt2[mans]) mans++;
for(rg int i=l;i<=r;i++){
cnt2[a[i]]--;
}
return mans;
}
int main(){
memset(lmax,0x3f,sizeof(lmax));
n=read(),q=read();
blo=sqrt(n);
for(rg int i=1;i<=n;i++){
a[i]=read();
shuyu[i]=(i-1)/blo+1;
}
for(rg int i=1;i<=n;i++){
rmax[shuyu[i]]=std::max(rmax[shuyu[i]],i);
lmax[shuyu[i]]=std::min(lmax[shuyu[i]],i);
}
for(rg int i=1;i<=q;i++){
b[i].l=read(),b[i].r=read(),b[i].id=i;
}
std::sort(b+1,b+1+q,cmp);
rg int nl=1,nr=0,now=1,tmp,cs;
for(rg int i=1;i<=shuyu[n];i++){
nans=0;
nr=n;
for(rg int j=lmax[i];j<=nr;j++) cnt[a[j]]++;
while(cnt[nans]) nans++;
while(shuyu[b[now].l]==i){
if(b[now].r-b[now].l<=blo){
ans[b[now].id]=solve(b[now].l,b[now].r);
now++;
continue;
}
nl=lmax[i];
while(nr>b[now].r){
sc(a[nr]);
nr--;
}
tmp=nans;
for(rg int j=nl;j<b[now].l;j++){
cnt3[a[j]]=cnt[a[j]];
}
cs=nl;
while(nl<b[now].l){
sc(a[nl]);
nl++;
}
for(rg int j=cs;j<b[now].l;j++){
cnt[a[j]]=cnt3[a[j]];
}
ans[b[now].id]=nans;
nans=tmp;
now++;
}
for(rg int j=lmax[i];j<=n;j++) cnt[a[j]]=0;
}
for(rg int i=1;i<=q;i++) printf("%d
",ans[i]);
return 0;
}
回滚莫队的复杂度和普通莫队是相同的
树上莫队
首先我们要把树变成一个序列
普通的 (dfn) 序可以处理子树上的问题
但是处理路径问题就要用到欧拉序
欧拉序的求法很简单，在刚 (dfs) 到一个点时加入序列，最后退出时也加入一遍
设 (eul1[i]) 表示访问到 (i) 时加入欧拉序的时间，(eul2[i]) 表示回溯经过 (i) 时加入欧拉序的时间
设 (eul1[x]<eul1[y])
若 (lca(x,y) = x)，这时 (x,y)在一条链上，那么(eul1[x]) 到 (eul1[y]) 这段区间中，有的点出现了两次，有的点没有出现过，这些点都是对答案没有贡献的，我们只需要统计出现过 (1) 次的点就好
若(lca(x,y) eq x)，此时 (x,y) 位于不同的子树内，我们只需要按照上面的方法统计 (eul2[x]) 到 (eul1[y]) 这段区间内的点，但是我们发现这里面的点不包括 (lca)，所以要把 (lca) 加上
代码
SP10707 COT2 - Count on a tree II
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int h[maxn],tot=1,n,q,blo,a[maxn],sta[maxn],tp2,eul1[maxn],eul2[maxn],dfn[maxn],dfnc;
bool vis[maxn];
struct asd{
int to,nxt;
}b[maxn];
void ad(rg int aa,rg int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int siz[maxn],dep[maxn],son[maxn],fa[maxn],rk[maxn],tp[maxn],nans,ans[maxn],cnt[maxn];
void dfs1(rg int now,rg int lat){
dep[now]=dep[lat]+1;
eul1[now]=++dfnc;
rk[dfnc]=now;
siz[now]=1;
fa[now]=lat;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
dfs1(u,now);
siz[now]+=siz[u];
if(siz[u]>siz[son[now]]) son[now]=u;
}
eul2[now]=++dfnc;
rk[dfnc]=now;
}
void dfs2(rg int now,rg int top){
tp[now]=top;
if(son[now]) dfs2(son[now],top);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa[now] || u==son[now]) continue;
dfs2(u,u);
}
}
int getlca(rg int xx,rg int yy){
while(tp[xx]!=tp[yy]){
if(dep[tp[xx]]<dep[tp[yy]]) std::swap(xx,yy);
xx=fa[tp[xx]];
}
if(dep[xx]<dep[yy]) return xx;
return yy;
}
int shuyu[maxn];
struct jie{
int l,r,id,anc;
jie(){}
jie(rg int aa,rg int bb,rg int cc,rg int dd){
l=aa,r=bb,id=cc,anc=dd;
}
}c[maxn];
bool cmp(rg jie aa,rg jie bb){
if(shuyu[aa.l]==shuyu[bb.l]){
return shuyu[aa.l]&1?aa.r<bb.r:aa.r>bb.r;
} else {
return shuyu[aa.l]<shuyu[bb.l];
}
}
void xg(rg int now){
rg int val=vis[now]?-1:1;
if(cnt[a[now]]==0) nans++;
cnt[a[now]]+=val;
if(cnt[a[now]]==0) nans--;
vis[now]^=1;
}
int main(){
memset(h,-1,sizeof(h));
n=read(),q=read();
blo=sqrt(n+n);
for(rg int i=1;i<=n;i++){
a[i]=read();
sta[++tp2]=a[i];
}
for(rg int i=1;i<=n+n;i++){
shuyu[i]=(i-1)/blo+1;
}
std::sort(sta+1,sta+1+tp2);
tp2=std::unique(sta+1,sta+1+tp2)-sta-1;
for(rg int i=1;i<=n;i++) a[i]=std::lower_bound(sta+1,sta+1+tp2,a[i])-sta;
rg int aa,bb,cc;
for(rg int i=1;i<n;i++){
aa=read(),bb=read();
ad(aa,bb);
ad(bb,aa);
}
dfs1(1,0);
dfs2(1,1);
for(rg int i=1;i<=q;i++){
aa=read(),bb=read();
if(eul1[aa]>eul1[bb]) std::swap(aa,bb);
cc=getlca(aa,bb);
if(cc==aa){
c[i]=jie(eul1[aa],eul1[bb],i,0);
} else {
c[i]=jie(eul2[aa],eul1[bb],i,cc);
}
}
std::sort(c+1,c+1+q,cmp);
rg int nl=1,nr=0;
for(rg int i=1;i<=q;i++){
while(nr<c[i].r) xg(rk[++nr]);
while(nl>c[i].l) xg(rk[--nl]);
while(nr>c[i].r) xg(rk[nr--]);
while(nl<c[i].l) xg(rk[nl++]);
if(c[i].anc) xg(c[i].anc);
ans[c[i].id]=nans;
if(c[i].anc) xg(c[i].anc);
}
for(rg int i=1;i<=q;i++){
printf("%d
",ans[i]);
}
return 0;
}