【bzoj3514】Codechef MARCH14 GERALD07加强版

hzwer上少有的几道需要建一下模的要不是有这么几道题我都觉得lct只会考裸题了呢
唯一蛋疼的就是为了处理0这个呵呵的位置，和严格小于，我把ntr数组全部+2，然后l+1,这样建树的时候就要写m+2了= =好蛋疼
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<cstdio>
  5 #include<algorithm>
  6 #include<cctype>
  7 
  8 using namespace std;
  9 
 10 const int Maxn=200020;
 11 const int logn=21;
 12 
 13 int a[Maxn],b[Maxn],ntr[Maxn];
 14 int n,m,k,type;
 15 
 16 template<typename Q> void gt(Q&x) {
 17     static char c;
 18     static bool f;
 19     for(f=0;c=getchar(),!isdigit(c);) if(c=='-') f=1;
 20     for(x=0;isdigit(c);c=getchar()) x=x*10+c-'0';
 21     f && (x=-x);
 22 }
 23 
 24 struct PST {
 25     int seq[Maxn];
 26     
 27     struct Node{
 28         Node *l,*r;
 29         int sz;
 30     }pool[Maxn*logn],*pis,*root[Maxn],*null;
 31     
 32     void build(Node*&o,Node *p,int l,int r,int rk) {
 33         o=pis++;
 34         *o=*p;
 35         o->sz++;
 36         if(l==r) return;
 37         int mid=(l+r)>>1;
 38         if(rk<=mid) build(o->l,p->l,l,mid,rk);
 39         else build(o->r,p->r,mid+1,r,rk);
 40     }
 41     
 42     void init() {
 43         pis=pool;
 44         memcpy(seq,ntr,sizeof seq);
 45         sort(seq+1,seq+m+1);
 46         null=pis++;
 47         null->l=null->r=null;
 48         null->sz=0;
 49         root[0]=null;
 50         for(int i=1;i<=m;i++) {
 51             build(root[i],root[i-1],1,m+2,ntr[i]);
 52         }
 53     }
 54     
 55     int query(Node*L,Node*R,int l,int r,int lft,int rgt) {
 56         if(lft<=l && r<=rgt) return R->sz - L->sz;
 57         int mid=(l+r)>>1;
 58         int ans=0;
 59         if(lft<=mid) ans+=query(L->l,R->l,l,mid,lft,rgt);
 60         if(mid<rgt) ans+=query(L->r,R->r,mid+1,r,lft,rgt);
 61         return ans;
 62     }
 63     
 64     int query(int l,int r,int x) {
 65         return query(root[l-1],root[r],1,m+2,1,x);
 66     }
 67 }pst;
 68 
 69 int ch[Maxn*2][2],w[Maxn*2],mn[Maxn*2],p[Maxn*2],flip[Maxn*2];
 70 
 71 #define l ch[x][0]
 72 #define r ch[x][1]
 73 void update(int x) {
 74     mn[x]=x;
 75     if(w[mn[l]]<w[mn[x]]) mn[x]=mn[l];
 76     if(w[mn[r]]<w[mn[x]]) mn[x]=mn[r];
 77 }
 78 
 79 void down(int x) {
 80     if(flip[x]) {
 81         swap(l,r);
 82         flip[l]^=1;
 83         flip[r]^=1;
 84         flip[x]^=1;
 85     }
 86 }
 87 #undef l
 88 #undef r
 89 
 90 bool isroot(int x) {
 91     return ch[p[x]][0]!=x && ch[p[x]][1]!=x;
 92 }
 93 
 94 void rotate(int x) {
 95     int y=p[x],z=p[y];
 96     if(!isroot(y)) ch[z][ch[z][1]==y]=x;
 97     int l=ch[y][1]==x,r=l^1;
 98     p[x]=z;
 99     p[y]=x;
100     p[ch[x][r]]=y;
101     
102     ch[y][l]=ch[x][r];
103     ch[x][r]=y;
104     
105     update(y);
106 //    update(x);
107 }
108 
109 void splay(int x) {
110     static int stk[Maxn],top;
111     stk[top=1]=x;
112     for(int t=x;!isroot(t);t=p[t]) stk[++top]=p[t];
113     while(top) down(stk[top--]);
114     
115     for(;!isroot(x);) {
116         int y=p[x],z=p[y];
117         if(!isroot(y)) {
118             if( (ch[y][0]==x)^(ch[z][0]==y) )rotate(x);
119             rotate(y);
120         }
121         rotate(x);
122     }
123     update(x);
124 }
125 
126 void access(int x) {
127     for(int t=0;x;x=p[t=x]) {
128         splay(x);
129         ch[x][1]=t;
130         update(x);
131     }
132 }
133 void newroot(int x) {
134     access(x);
135     splay(x);
136     flip[x]^=1;
137 }
138 
139 void Link(int x,int y) {
140     newroot(x);
141     p[x]=y;
142 }
143 
144 void Cut(int x,int y) {
145     newroot(y);
146     access(x);
147     splay(x);
148     if(ch[x][0]==y) {
149         ch[x][0]=0;
150         p[y]=0;
151         update(x);
152     }
153 }
154 
155 int getroot(int x) {
156     for(access(x),splay(x);ch[x][0];x=ch[x][0]);
157     return x;
158 }
159 
160 const int INF=0x3f3f3f3f;
161 
162 void init() {
163     scanf("%d%d%d%d",&n,&m,&k,&type);
164     for(int i=0;i<=n;i++) {
165         w[i]=INF;
166         mn[i]=i;
167     }
168     for(int x,y,i=1;i<=m;i++) {
169 //        scanf("%d%d",a+i,b+i);
170         gt(a[i]),gt(b[i]);
171         x=a[i],y=b[i];
172         if(x==y) {
173             ntr[i]=i;
174             continue;
175         }
176         if(getroot(x)==getroot(y)) {
177             newroot(y);
178             access(x);
179             splay(x);
180             int t=mn[x];
181             ntr[i]=w[t];
182             Cut(t,a[w[t]]);
183 //            Cut(t,b[w[t]]);
184         }
185         mn[i+n]=i+n;
186         w[i+n]=i;
187         Link(x,i+n);
188         Link(y,i+n);
189     }
190     for(int i=1;i<=m;i++) ntr[i]+=2;
191     pst.init();
192 }
193 
194 void work() {
195     for(int l,r,last_ans=0;k--;) {
196 //        scanf("%d%d",&l,&r);
197         gt(l),gt(r);
198         if(type) l^=last_ans,r^=last_ans;
199         
200         last_ans=n-pst.query(l,r,l+1);
201         printf("%d
",last_ans);
202     }
203 }
204 
205 void PST_test() {
206     scanf("%d",&m);
207     for(int i=1;i<=m;i++) {
208         scanf("%d",ntr+i);
209     }
210     for(int i=1;i<=m;i++) ntr[i]+=2;
211     pst.init();
212     for(scanf("%d",&k);k--;) {
213         int x,y,w;
214         scanf("%d%d%d",&x,&y,&w);w++;
215         printf("%d
",pst.query(x,y,w));
216     }
217 }
218 
219 int main() {
220 #ifdef DEBUG
221     freopen("in.txt","r",stdin);
222 //    freopen("out.txt","w",stdout);
223 #endif
224     
225 //    PST_test();return 0;
226     
227     init();
228     work();
229     
230     return 0;
231 }
View Code