hzwer上少有的几道需要建一下模的 要不是有这么几道题 我都觉得lct只会考裸题了呢
题解看hzwer吧 http://hzwer.com/4358.html
唯一蛋疼的就是为了处理0这个呵呵的位置，和严格小于，我把ntr数组全部+2，然后l+1,这样建树的时候就要写m+2了= =好蛋疼
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cctype> using namespace std; const int Maxn=;
const int logn=; int a[Maxn],b[Maxn],ntr[Maxn];
int n,m,k,type; template<typename Q> void gt(Q&x) {
static char c;
static bool f;
for(f=;c=getchar(),!isdigit(c);) if(c=='-') f=;
for(x=;isdigit(c);c=getchar()) x=x*+c-'';
f && (x=-x);
} struct PST {
int seq[Maxn]; struct Node{
Node *l,*r;
int sz;
}pool[Maxn*logn],*pis,*root[Maxn],*null; void build(Node*&o,Node *p,int l,int r,int rk) {
o=pis++;
*o=*p;
o->sz++;
if(l==r) return;
int mid=(l+r)>>;
if(rk<=mid) build(o->l,p->l,l,mid,rk);
else build(o->r,p->r,mid+,r,rk);
} void init() {
pis=pool;
memcpy(seq,ntr,sizeof seq);
sort(seq+,seq+m+);
null=pis++;
null->l=null->r=null;
null->sz=;
root[]=null;
for(int i=;i<=m;i++) {
build(root[i],root[i-],,m+,ntr[i]);
}
} int query(Node*L,Node*R,int l,int r,int lft,int rgt) {
if(lft<=l && r<=rgt) return R->sz - L->sz;
int mid=(l+r)>>;
int ans=;
if(lft<=mid) ans+=query(L->l,R->l,l,mid,lft,rgt);
if(mid<rgt) ans+=query(L->r,R->r,mid+,r,lft,rgt);
return ans;
} int query(int l,int r,int x) {
return query(root[l-],root[r],,m+,,x);
}
}pst; int ch[Maxn*][],w[Maxn*],mn[Maxn*],p[Maxn*],flip[Maxn*]; #define l ch[x][0]
#define r ch[x][1]
void update(int x) {
mn[x]=x;
if(w[mn[l]]<w[mn[x]]) mn[x]=mn[l];
if(w[mn[r]]<w[mn[x]]) mn[x]=mn[r];
} void down(int x) {
if(flip[x]) {
swap(l,r);
flip[l]^=;
flip[r]^=;
flip[x]^=;
}
}
#undef l
#undef r bool isroot(int x) {
return ch[p[x]][]!=x && ch[p[x]][]!=x;
} void rotate(int x) {
int y=p[x],z=p[y];
if(!isroot(y)) ch[z][ch[z][]==y]=x;
int l=ch[y][]==x,r=l^;
p[x]=z;
p[y]=x;
p[ch[x][r]]=y; ch[y][l]=ch[x][r];
ch[x][r]=y; update(y);
// update(x);
} void splay(int x) {
static int stk[Maxn],top;
stk[top=]=x;
for(int t=x;!isroot(t);t=p[t]) stk[++top]=p[t];
while(top) down(stk[top--]); for(;!isroot(x);) {
int y=p[x],z=p[y];
if(!isroot(y)) {
if( (ch[y][]==x)^(ch[z][]==y) )rotate(x);
rotate(y);
}
rotate(x);
}
update(x);
} void access(int x) {
for(int t=;x;x=p[t=x]) {
splay(x);
ch[x][]=t;
update(x);
}
}
void newroot(int x) {
access(x);
splay(x);
flip[x]^=;
} void Link(int x,int y) {
newroot(x);
p[x]=y;
} void Cut(int x,int y) {
newroot(y);
access(x);
splay(x);
if(ch[x][]==y) {
ch[x][]=;
p[y]=;
update(x);
}
} int getroot(int x) {
for(access(x),splay(x);ch[x][];x=ch[x][]);
return x;
} const int INF=0x3f3f3f3f; void init() {
scanf("%d%d%d%d",&n,&m,&k,&type);
for(int i=;i<=n;i++) {
w[i]=INF;
mn[i]=i;
}
for(int x,y,i=;i<=m;i++) {
// scanf("%d%d",a+i,b+i);
gt(a[i]),gt(b[i]);
x=a[i],y=b[i];
if(x==y) {
ntr[i]=i;
continue;
}
if(getroot(x)==getroot(y)) {
newroot(y);
access(x);
splay(x);
int t=mn[x];
ntr[i]=w[t];
Cut(t,a[w[t]]);
// Cut(t,b[w[t]]);
}
mn[i+n]=i+n;
w[i+n]=i;
Link(x,i+n);
Link(y,i+n);
}
for(int i=;i<=m;i++) ntr[i]+=;
pst.init();
} void work() {
for(int l,r,last_ans=;k--;) {
// scanf("%d%d",&l,&r);
gt(l),gt(r);
if(type) l^=last_ans,r^=last_ans; last_ans=n-pst.query(l,r,l+);
printf("%d\n",last_ans);
}
} void PST_test() {
scanf("%d",&m);
for(int i=;i<=m;i++) {
scanf("%d",ntr+i);
}
for(int i=;i<=m;i++) ntr[i]+=;
pst.init();
for(scanf("%d",&k);k--;) {
int x,y,w;
scanf("%d%d%d",&x,&y,&w);w++;
printf("%d\n",pst.query(x,y,w));
}
} int main() {
#ifdef DEBUG
freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
#endif // PST_test();return 0; init();
work(); return ;
}