1： P11071 「QMSOI R1」 Distorted Fate
二进制的题，优先想到拆位求贡献。
因为是或，对于某一位，找到区间中最左的这一位为 \(1\) 的位置，然后相应的乘上它到右端点的距离，就可以计算答案了。
\(logV\) 是 \(30\)，可以想到对二进制的每一位开一棵线段树，维护区间中这一位相关信息。
然后就是经典的线段树二分，很可惜这题空间有限。
不过我们发现，只关心区间中有没有 \(1\)，所以直接用bool代替整形变量即可。
维护区间按位与和，按位或和，只在这两个值相等时更新，然后查询时依然线段树二分，不过实现细节与之前有所不同。
时空复杂度均为 \(O(n\space logn\space logV)\)。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
const int N=2e5+10,M=30,mod=(1<<M);
int n,a[N],q;
struct SMT{
struct node{bool x,y,tag;}tr[N<<2];
void pushdown(int u){
if(!tr[u].tag) return;
if(tr[u<<1].x==tr[u<<1].y) tr[u<<1].x^=1,tr[u<<1].y^=1;
if(tr[u<<1|1].x==tr[u<<1|1].y) tr[u<<1|1].x^=1,tr[u<<1|1].y^=1;
tr[u<<1].tag^=1,tr[u<<1|1].tag^=1,tr[u].tag=0;
}
void pushup(int u){
tr[u].x=tr[u<<1].x|tr[u<<1|1].x;
tr[u].y=tr[u<<1].y&tr[u<<1|1].y;
}
void build(int u,int l,int r){
if(l==r){tr[u].x=tr[u].y=a[l]&1;return;}
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r),pushup(u);
}
void modify(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
if(tr[u].x==tr[u].y) tr[u].x^=1,tr[u].y^=1;
tr[u].tag^=1;return;
}
pushdown(u);int mid=(l+r)>>1;
if(ql<=mid) modify(u<<1,l,mid,ql,qr);
if(qr>mid) modify(u<<1|1,mid+1,r,ql,qr);
pushup(u);
}
int find(int u,int l,int r){
if(l==r) return l;
pushdown(u);int mid=(l+r)>>1;
if(tr[u<<1].x) return find(u<<1,l,mid);
return find(u<<1|1,mid+1,r);
}
int query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
if(tr[u].x) return find(u,l,r);
return -1;
}
if(r<ql||l>qr) return -1;
pushdown(u);int mid=(l+r)>>1,ans=-1;
if(ql<=mid) ans=query(u<<1,l,mid,ql,qr);
if(ans!=-1) return ans;
if(qr>mid) ans=query(u<<1|1,mid+1,r,ql,qr);
return ans;
}
}S[M];
int main(){
n=rd,q=rd;FOR(i,1,n) a[i]=rd;
FOR(i,0,M-1){
S[i].build(1,1,n+1);
FOR(j,1,n) a[j]>>=1;
}
while(q--){
int op=rd,l=rd,r=rd;
if(op==1){
int x=rd;
FOR(i,0,M-1){
if(x&1) S[i].modify(1,1,n+1,l,r);
x>>=1;
}
}
else{
int ans=0;
FOR(i,0,M-1){
int pos=S[i].query(1,1,n+1,l,r);
if(pos!=-1) ans=(ans+(1ll<<i)*(r-min(r+1,pos)+1)%mod)%mod;
}
printf("%d\n",ans);
}
}
return 0;
}
2：P4314 CPU 监控
区间加、区间赋值、区间最大值、区间历史最大值。
本题难点主要在 pushdown 操作和懒标记的下传。
当然用矩阵就不用思考这么多了:
-
用广义矩阵乘法 \(C_{i,j}=\max_{k=1}^{m}(A_{i,k}+B_{k,j})\)。
-
对区间加和区间赋值分别构造两个转移矩阵。
-
线段树维护的矩阵为 \(\begin{bmatrix}mx & smx & 0\end{bmatrix}\)，分别为区间最大值，区间历史最大值，以及 \(0\) 方便转移。
然后就做完了，难点来到卡常——不过这题太水，连卡常都不需要。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
const int N=1e5+10;
const ll INF=1e12;
int n,q,a[N];
struct matrix{
ll a[3][3];
matrix(){memset(a,0,sizeof(a));}
matrix operator+(matrix const &T){
matrix res;
FOR(i,0,2) FOR(j,0,2) res.a[i][j]=max(a[i][j],T.a[i][j]);
return res;
}
matrix operator*(matrix const &T){
matrix res;
FOR(i,0,2) FOR(j,0,2) res.a[i][j]=-INF;
FOR(i,0,2) FOR(j,0,2){
res.a[i][j]=max(res.a[i][j],a[i][0]+T.a[0][j]);
res.a[i][j]=max(res.a[i][j],a[i][1]+T.a[1][j]);
res.a[i][j]=max(res.a[i][j],a[i][2]+T.a[2][j]);
}
return res;
}
bool operator==(matrix const &T){
FOR(i,0,2) FOR(j,0,2) if(a[i][j]!=T.a[i][j]) return false;
return true;
}
}mx[N<<2],tag[N<<2],I,A;
matrix get_I(){
matrix res;
FOR(i,0,2) FOR(j,0,2) res.a[i][j]=-INF;
FOR(i,0,2) res.a[i][i]=0;
return res;
}
inline void pushdown(int u){
if(tag[u]==I) return;
tag[u<<1]=tag[u<<1]*tag[u],tag[u<<1|1]=tag[u<<1|1]*tag[u];
mx[u<<1]=mx[u<<1]*tag[u],mx[u<<1|1]=mx[u<<1|1]*tag[u];
tag[u]=I;
}
inline void build(int u,int l,int r){
tag[u]=I;
if(l==r){
mx[u].a[0][0]=mx[u].a[0][1]=a[l],mx[u].a[0][2]=0;
return;
}
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
mx[u]=mx[u<<1]+mx[u<<1|1];
}
inline void modify(int u,int l,int r,int ql,int qr,matrix v){
if(ql<=l&&r<=qr){
mx[u]=mx[u]*v,tag[u]=tag[u]*v;
return;
}
pushdown(u);int mid=(l+r)>>1;
if(ql<=mid) modify(u<<1,l,mid,ql,qr,v);
if(qr>mid) modify(u<<1|1,mid+1,r,ql,qr,v);
mx[u]=mx[u<<1]+mx[u<<1|1];
}
matrix query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return mx[u];
pushdown(u);int mid=(l+r)>>1;matrix res=A;
if(ql<=mid) res=res+query(u<<1,l,mid,ql,qr);
if(qr>mid) res=res+query(u<<1|1,mid+1,r,ql,qr);
return res;
}
int main(){
n=rd,I=get_I();FOR(i,1,n) a[i]=rd;
build(1,1,n);
FOR(i,0,2) FOR(j,0,2) A.a[i][j]=-INF;
q=rd;
while(q--){
char op=getchar();int l=rd,r=rd;
matrix res=query(1,1,n,l,r);
if(op=='Q') printf("%lld\n",res.a[0][0]);
else if(op=='A') printf("%lld\n",res.a[0][1]);
else if(op=='P'){
int x=rd;matrix v;
v.a[0][0]=x,v.a[1][0]=v.a[2][0]=-INF,v.a[0][1]=x,v.a[0][2]=-INF,v.a[1][1]=v.a[2][2]=0,v.a[1][2]=v.a[2][1]=-INF;
modify(1,1,n,l,r,v);
}
else{
int x=rd;matrix v;
v.a[0][0]=v.a[0][1]=v.a[0][2]=v.a[1][0]=v.a[1][2]=-INF,v.a[1][1]=0,v.a[2][0]=v.a[2][1]=x,v.a[2][2]=0;
modify(1,1,n,l,r,v);
}
}
return 0;
}
3：GSS2 - Can you answer these queries II
不算重复数字，按 HH 的项链的思路，很容易想到询问离线，右端点从小到大枚举。
主要还是最大子段和的计算，不能用之前的方法。
我们考虑当前右端点枚举到 \(i\)，然后记 \(la_i=j\) 表示最近的 \(a_j=a_i\) 的 \(j\)，然后区间 \([la_i+1,i]\) 加 \(a_i\)。
这时我们发现一个位置 \(j\) 上的数，就表示去重后的 \(\sum_{k=j}^{i}a_k\)，对于询问 \([l,r],r=i\)，查询 \([l,r]\) 中最大值即可。
然而这样还是错的，因为最大子段和不一定以 \(r\) 为右端点，所以我们再维护历史最大值即可。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define PII pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
const int N=2e5+10,INF=1e5;
int n,a[N],la[N],q;ll ans[N],smx[N<<2],hs[N<<2],tag1[N<<2],tag2[N<<2];
vector<PII> ve[N];
void pushdown(int u){
hs[u<<1]=max(hs[u<<1],smx[u<<1]+tag2[u]),hs[u<<1|1]=max(hs[u<<1|1],smx[u<<1|1]+tag2[u]);
tag2[u<<1]=max(tag2[u<<1],tag1[u<<1]+tag2[u]),tag2[u<<1|1]=max(tag2[u<<1|1],tag1[u<<1|1]+tag2[u]);
smx[u<<1]+=tag1[u],smx[u<<1|1]+=tag1[u];
tag1[u<<1]+=tag1[u],tag1[u<<1|1]+=tag1[u];
tag1[u]=tag2[u]=0;
}
void pushup(int u){
smx[u]=max(smx[u<<1],smx[u<<1|1]);
hs[u]=max(hs[u<<1],hs[u<<1|1]);
}
void modify(int u,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
smx[u]+=v,hs[u]=max(hs[u],smx[u]);
tag1[u]+=v,tag2[u]=max(tag2[u],tag1[u]);
return;
}
pushdown(u);int mid=(l+r)>>1;
if(ql<=mid) modify(u<<1,l,mid,ql,qr,v);
if(qr>mid) modify(u<<1|1,mid+1,r,ql,qr,v);
pushup(u);
}
ll query(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return hs[u];
pushdown(u);int mid=(l+r)>>1;ll ans=0;
if(ql<=mid) ans=max(ans,query(u<<1,l,mid,ql,qr));
if(qr>mid) ans=max(ans,query(u<<1|1,mid+1,r,ql,qr));
return ans;
}
int main(){
n=rd;FOR(i,1,n) a[i]=rd;
q=rd;FOR(i,1,q){int l=rd,r=rd;ve[r].push_back(mp(l,i));}
FOR(i,1,n){
modify(1,1,n,la[a[i]+INF]+1,i,a[i]),la[a[i]+INF]=i;
for(auto j:ve[i]) ans[j.se]=query(1,1,n,j.fi,i);
}
FOR(i,1,q) printf("%lld\n",max(0ll,ans[i]));
return 0;
}
4：P3081 [USACO13MAR] Hill Walk G
发现对于某条线段 \((x_0,y_0),(x_1,y_1)\)，只有满足 \(x_0'\le x_1,x_1'>x_1\)，且在 \(x=x_1\) 处的 \(y\) 值 \(\le y_1\) 的线段，才可以被降落到。
然后我们需要在这些线段中查询 \(x=x_1\) 时纵坐标最大的线段编号，这是李超线段树的经典操作。
因为随着走动， \(x\) 是不断增大的，所以按 \(x_0\) 排序，将满足条件的线段逐个加入，最后更新所在线段即可。
动态开点会 MLE，需要先将横坐标离散化。
本题细节有些多，需要注意只在李超线段树上修改查询时用离散化后的横坐标，其他时候任何计算，都用原来的坐标值。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define PDI pair<double,int>
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
#define debug cout<<"ILOVECCF!"<<endl;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
const int N=3e5+10;
const double eps=1e-10,INF=2e18;
int n,seg[N<<2],lsh[N],cnt,tot,ld[N];
struct node{int x0,y0,x1,y1,l,r,t;}s[N];
bool cmp_s(node a,node b){
if(a.x0!=b.x0) return a.x0<b.x0;
return a.y1>b.y1;
}
struct segment{double k,b;}p[N];
double cal(int id,int x){return p[id].k*x+p[id].b;}
int cmp(double x,double y){
if(x-y>eps) return 1;
if(y-x>eps) return -1;
return 0;
}
void update(int u,int l,int r,int id){
int &g=seg[u],mid=(l+r)>>1;
if(cmp(cal(id,lsh[mid]),cal(g,lsh[mid]))==1) swap(g,id);
if(cmp(cal(id,lsh[l]),cal(g,lsh[l]))==1) update(u<<1,l,mid,id);
if(cmp(cal(id,lsh[r]),cal(g,lsh[r]))==1) update(u<<1|1,mid+1,r,id);
}
void modify(int u,int l,int r,int ql,int qr,int id){
if(ql<=l&&r<=qr){update(u,l,r,id);return;}
int mid=(l+r)>>1;
if(ql<=mid) modify(u<<1,l,mid,ql,qr,id);
if(qr>mid) modify(u<<1|1,mid+1,r,ql,qr,id);
}
PDI pmx(PDI a,PDI b){
if(cmp(a.fi,b.fi)==1) return a;
return b;
}
PDI query(int u,int l,int r,int v){
if(l>v||r<v) return mp(-INF,0);
int mid=(l+r)>>1;PDI res=mp(cal(seg[u],lsh[v]),seg[u]);
if(l==r) return res;
return pmx(res,pmx(query(u<<1,l,mid,v),query(u<<1|1,mid+1,r,v)));
}
void make_seg(int x0,int y0,int x1,int y1){
double k=1.0*(y1-y0)/(x1-x0),b=-k*x0+1.0*y0;
p[++cnt]={k,b};
}
int main(){
n=rd;
FOR(i,1,n) s[i].x0=rd,s[i].y0=rd,s[i].x1=rd,s[i].y1=rd,lsh[++cnt]=s[i].x0,lsh[++cnt]=s[i].x1,lsh[++cnt]=s[i].x1-1,s[i].l=s[i].x0,s[i].r=s[i].x1,s[i].t=s[i].x1-1;
sort(lsh+1,lsh+1+cnt),tot=unique(lsh+1,lsh+1+cnt)-lsh-1;
sort(s+1,s+1+n,cmp_s),cnt=0;int idx=1,ans=1;
FOR(i,1,n) s[i].l=lower_bound(lsh+1,lsh+1+tot,s[i].l)-lsh,s[i].r=lower_bound(lsh+1,lsh+1+tot,s[i].r)-lsh,s[i].t=lower_bound(lsh+1,lsh+1+tot,s[i].t)-lsh;
FOR(i,1,n) make_seg(s[i].x0,s[i].y0,s[i].x1,s[i].y1);
p[0].b=-INF;
for(int i=2;;){
for(;i<=n;i++){
if(s[i].x0>s[idx].x1) break;
if(s[i].x1<=s[idx].x1||cal(i,s[idx].x1)>s[idx].y1) continue;
modify(1,1,tot,s[i].l,s[i].t,i);
}
int pos=query(1,1,tot,s[idx].r).se;
if(!pos) break;
ans++,idx=pos;
}
printf("%d\n",ans);
return 0;
}
5：P11203 [JOIG 2024] 感染シミュレーション
容易发现，感染者存在的时间一定是一段连续的区间，考虑找到这些区间 \([s,t]\)，然后问题就变为有多少右端点在 \([s,t]\) 中，且长度 \(\ge x\) 的线段，这是经典的二维偏序问题。
首先解决问题一，如何找到这些区间？不难发现，对于某条线段 \([l_i,r_i]\)，我们只看 \(r_j>r_i\) 的 \(l_j\) 最小的线段，因为这样它们的交集才最大，如果这都不满足 \(\ge x\) 的条件的话，之后的传染就直接断了。
所以对于每条线段，先找到符合上述条件的线段作为它的后继，接下来可以倍增找到最后的满足条件的线段，只需判断交集最小值即可。
问题一解决，再考虑问题二，二维偏序问题，把所有询问离线下来，然后注意离散化即可。
特别地，离散化数组注意开到 \(4n\)，因为要存的有询问左端点、右端点、区间长度、\(x-1\)（\(-1\) 是为了差分）这些值。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
const int N=1e5+10;
int n,f[N][20],fmn[N][20],q,lsh[N<<2],cnt,tot,id[N],tr[N<<2],ans[N];
struct node{int l,r;}seg[N];
bool cmp(int a,int b){return seg[a].r<seg[b].r;}
struct quest{int l,r,x;}que[N<<2];
struct Node{int id,x,op;};
vector<int> c[N<<2];vector<Node> v[N<<2];
int lowbit(int x){return x&-x;}
void add(int x,int v){for(int i=x;i<=tot;i+=lowbit(i))tr[i]+=v;}
int query(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
int main(){
n=rd;
FOR(i,1,n) seg[i].l=rd,seg[i].r=rd,id[i]=i,lsh[++cnt]=seg[i].r,lsh[++cnt]=seg[i].r-seg[i].l;
sort(id+1,id+1+n,cmp);int pos=n,to=id[pos];
ROF(i,n,1){
while(pos>0&&seg[id[pos]].r>seg[id[i]].r){
if(seg[id[pos]].l<seg[to].l) to=id[pos];
pos--;
}
f[id[i]][0]=to,fmn[id[i]][0]=seg[id[i]].r-seg[to].l;
FOR(j,1,18) f[id[i]][j]=f[f[id[i]][j-1]][j-1],fmn[id[i]][j]=min(fmn[id[i]][j-1],fmn[f[id[i]][j-1]][j-1]);
}
q=rd;
FOR(i,1,q){
int P=rd,x=rd,t=P;
if(seg[P].r-seg[P].l<x){ans[i]=1;continue;}
ROF(j,18,0) if(fmn[t][j]>=x) t=f[t][j];
que[i]={seg[P].l+x-1,seg[t].r,x},lsh[++cnt]=seg[P].l+x-1,lsh[++cnt]=x-1;
}
sort(lsh+1,lsh+1+cnt),tot=unique(lsh+1,lsh+1+cnt)-lsh-1;cnt=0;
FOR(i,1,q){
if(ans[i]) continue;
que[i].l=lower_bound(lsh+1,lsh+1+tot,que[i].l)-lsh;
que[i].r=lower_bound(lsh+1,lsh+1+tot,que[i].r)-lsh;
que[i].x=lower_bound(lsh+1,lsh+1+tot,que[i].x-1)-lsh;
int l=que[i].l,r=que[i].r,x=que[i].x;
v[l].push_back({i,x,-1}),v[r].push_back({i,x,1});
}
FOR(i,1,n){
int x=lower_bound(lsh+1,lsh+1+tot,seg[i].r)-lsh;
int y=lower_bound(lsh+1,lsh+1+tot,seg[i].r-seg[i].l)-lsh;
c[x].push_back(y);
}
int sum=0;
FOR(i,1,tot){
for(auto j:c[i]) add(j,1),sum++;
for(auto j:v[i]){
ans[j.id]+=j.op*(sum-query(j.x));
}
}
FOR(i,1,q) printf("%d\n",ans[i]);
return 0;
}
6：P11191 「KDOI-10」超级演出
二维偏序+根号分治。
首先发现对于第 \(i\) 个命令，会存在一个 \(w_i\) 使得执行完 \([w_i,i)\) 的命令后使得第 \(i\) 个命令的剧团能够出场。
如果 \(a_i\) 能直接到达 \(1\)，显然 \(w_i=i\)，否则 \(a_i=\max_{a_i\to v}\{w_v\}\)。
然后对于询问 \([l,r]\)，需要满足 \(i\in [l,r],w_i\ge l\) 才可以出场，最终这段区间答案为 \(n-1-query(l,r)\)，因为求的是候场的，这是经典二维偏序，离线询问枚举右端点可以 \(O(nlogn)\) 完成。
发现时间复杂度瓶颈在于求 \(w\) 数组，因为某个点出度可能非常大。但是我们发现出度大的点不会很多，这时候就可以考虑根号分治了。
设阈值 \(B\)，对于出度 \(\le B\) 暴力计算，对于 \(\ge B\) 的点我们不去暴力算它，而是通过其他点对其更新。
时间复杂度 \(O(\frac{n^2}{B}+nB)\)，利用基本不等式不难算出 \(B=\sqrt{n}\) 时最优。
#include<bits/stdc++.h>
using namespace std;
#define rd read()
#define ll long long
#define PII pair<int,int>
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define ROF(i,j,k) for(int i=j;i>=k;i--)
#define debug cout<<"FUCKCCF!!!"<<endl;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
const int N=4e5+10,M=450;
int c,n,m,k,q,cnt,deg[N],big[N],a[N],w[N],nxt[N],ans[N],tr[N],vis[N],la[N];
vector<int> v[N],e[N];vector<PII> que[N];
int lowbit(int x){return x&-x;}
void add(int x,int v){x++;for(int i=x;i<=k;i+=lowbit(i))tr[i]+=v;}
int query(int x){int res=0;x++;for(int i=x;i;i-=lowbit(i))res+=tr[i];return res;}
int main(){
c=rd,n=rd,m=rd,k=rd,q=rd;int t=sqrt(m);
FOR(i,1,m){int x=rd,y=rd;deg[x]++,v[x].push_back(y),vis[x]|=(y==1);}
FOR(i,1,n) if(deg[i]>=t) big[i]=1;
FOR(i,1,n){
if(!big[i]) continue;
for(auto j:v[i]) e[j].push_back(i);
}
FOR(i,1,k){
a[i]=rd;
if(vis[a[i]]) w[i]=i;
else if(deg[a[i]]<t){for(auto j:v[a[i]]) w[i]=max(w[i],la[j]);}
else w[i]=nxt[a[i]];
la[a[i]]=w[i];
for(auto j:e[a[i]]) nxt[j]=max(nxt[j],w[i]);
}
FOR(i,1,q){
int l=rd,r=rd;
que[r].push_back(make_pair(l,i));
}
memset(la,0,sizeof(la));
FOR(i,1,k){
add(w[la[a[i]]],1),add(w[i],-1),la[a[i]]=i;
for(auto j:que[i]){
ans[j.second]=n-1-query(j.first-1);
}
}
FOR(i,1,q) printf("%d\n",ans[i]);
return 0;
}