题意：

今天停电了，阅览室里的大家陷入了无电可用的状态，F发现他们桌子用的备用电源还在工作，于是大家就顺着这个备用电源用插线板连起了一条长链。
容易看出插线板的结构会形成一棵树（一个插线板所插在的插线板记为它的父节点，根节点为备用电源），但是大家不会把自己的插线板一直放在阅览室里（离开的时候就带走了），因此会出现树结构中某个节点消失的情况，而之后对树结构的修复方案很多会导致大家的混乱。因此F决定把插线板摆成一条链。F收集了所有带插线板来阅览室的同学的情况，把这些插线板排成了一条链并把它们从小到大编号，i号插线板会在第Li个时刻被一个来阅览室的同学带来，在第Ri个时刻拿走。我们规定0号插线板为备用电源（显然电源是一直可用的）。
当一个插线板被带来的时候，它会插到它左面的相邻插线板上，而它右面相邻的插线板会插到它上。当一个插线板被带走的时候，它右面相邻的插线板会插到它左面相邻的插线板上。也就是说这两种行为都会导致右面的插线板的插头的移动。这种移动会导致接在这个插线板的用电器也需要配合移动。（其他插线板和用电器不会受到影响）
F也收集了所有要用电的同学的情况。有Q个用电的同学想询问，如果他们在 [L,R] 的时刻用电，那么选择哪个插线板可以最小化他们用电器的移动次数。
虽然电源被我们看成0号插线板但是用电器不能接在备用电源上，即使此时一个插线板都没有也不行。

题解：
忽略边界条件吧， 大概就是有 n" role="presentation" style="position: relative;">n$n$个集合，每个集合里面有一些[li,ri]" role="presentation" style="position: relative;">[li,ri]$[l_i,r_i]$的数，每次询问L,R" role="presentation" style="position: relative;">L,R$L,R$ ，求li≤L,R≤ri" role="presentation" style="position: relative;">li≤L,R≤ri$l_i\le L,R\le r_i$的集合中[L,R]" role="presentation" style="position: relative;">[L,R]$[L,R]$的数的个数的最小值。 可以分块来做， 先处理出 询问为[i∗N,j]" role="presentation" style="position: relative;">[i∗N‾‾√,j]$[i\ast \sqrt{N},j]$的答案， 注意因为要求最小值，我们可以在询问的时候先询问包含L,R" role="presentation" style="position: relative;">L,R$L,R$的大区间的最小值， 再往内部挪动， 这样如果有比原来的最小值更优的值一定会在挪动的时候更新。
（同理最大值只需要先求小区间再往外挪动）
最后注意在挪动的时候要把那些li≤L" role="presentation" style="position: relative;">li≤L$l_i\le L$的区间给算进来，我们还需要用一个可持久化数组。 直接每个前缀记N" role="presentation" style="position: relative;">N‾‾√$\sqrt{N}$个int" role="presentation" style="position: relative;">int$int$数组的指针，每次复制前面的指针并复制一块新的数组来修改即可。 时间复杂度O(nn)" role="presentation" style="position: relative;">O(nn‾√)$O(n\sqrt{n})$ #include using namespace std; const int RLEN=1<<18|1, N=1e5+50, B=333, INF=0x3f3f3f3f; typedef set <int> Set; typedef Set ::iterator it_s; typedef pair<int,int> pii; inline char nc() { static char ibuf[RLEN],*ib,*ob; (ib==ob)?(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin)):0; return (ib==ob)?-1:*ib++; } inline int rd() { char ch=nc(); int i=0,f=1; while(!isdigit(ch)) {if(ch==-1) return 0; if(ch=='-')f=-1; ch=nc();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();} return i*f; } int n,m,q,type,tot,a[N],b[N],L[N],R[N],sum[N],res[N/B+2][N],lst; pii c[N]; struct BL { int *s[N/B+2]; inline void add(int x) { int k=x/B, p=x%B; int *t=(int *)malloc(sizeof(int)*B); if(s[k]==NULL) memset(t,0,sizeof(int)*B); else memcpy(t,s[k],sizeof(int)*B); ++t[p]; s[k]=t; } inline int ask(int x) { return (s[x/B]==NULL)?0:s[x/B][x%B]; } }pre[N]; Set S; int main() { n=rd(), m=rd(), q=rd(), type=rd(); for(int i=1;i<=n;i++) { L[i]=rd(), R[i]=rd(); a[L[i]]=i; a[R[i]]=-i; c[++tot]=pii(L[i],i); c[++tot]=pii(R[i],-i); } sort(c+1,c+tot+1); for(int i=1;i<=tot;i++) { it_s t=S.upper_bound(abs(c[i].second)); if(t!=S.end()) b[c[i].first]=*t;//, cerr<<*t<<" "<<(c[i].second<0)+c[i].first< (c[i].second<0)?(S.erase(-c[i].second),0):(S.insert(c[i].second),0); } for(int i=1;i<=m;i++) { pre[i]=pre[i-1]; if(c[i-1].second<0 && b[i-1]) pre[i].add(b[i-1]); if(c[i].second>0 && b[i]) pre[i].add(b[i]); } for(int i=1;i<=m;i+=B) { for(int j=i+1;j<=m;j++) { if(a[j-1]<0 && b[j-1]) ++sum[b[j-1]]; if(a[j]>0 && b[j]) ++sum[b[j]]; } int mn=INF; for(int j=m;j>i;j--) { if(a[j]<0 && L[-a[j]]<=i) mn=min(mn,sum[-a[j]]); //R>=r res[i/B][j]=mn; if(a[j]>0 && b[j]) --sum[b[j]], mn=min(mn,(L[b[j]]<=i)?sum[b[j]]:INF); if(a[j-1]<0 && b[j-1]) --sum[b[j-1]], mn=min(mn,(L[b[j-1]]<=i)?sum[b[j-1]]:INF); //若b_j有变动 则 R[b_j]>r, 且可能更新答案 } res[i/B][i]=mn; } for(int i=1;i<=q;i++) { int l=rd()^(type*lst), r=rd()^(type*lst); int k=(l-1)/B, mn=res[k][r]; //最优值只会比 mn 更优 for(int j=k*B+1;j<=l;j++) { if(a[j-1]<0 && b[j-1] && R[b[j-1]]>=r) mn=min(mn, pre[r].ask(b[j-1])-pre[l].ask(b[j-1])); if(a[j]>0 && b[j] && R[b[j]]>=r) mn=min(mn, pre[r].ask(b[j])-pre[l].ask(b[j])); //删去一个数 if(a[j]>0 && R[a[j]]>=r) mn=min(mn, pre[r].ask(a[j])-pre[l].ask(a[j])); //L<=l } if(mn==INF) puts("-1"), lst=0; else printf("%d ",lst=mn); } }