[BZOJ 2819]Nim

最近都忙的没空写题解了喵~

看到 1= 终于是保住了也算是一个小小的安慰吧 555……

湖北省队互测题,据说会爆栈,但 Linux 下 栈空间=内存=128M 真的吃不下?

反正我是写了个人工栈~

这似乎是我近 4 天里写的第 3 道树链剖分?

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 const int sizeOfPoint=500005;
  5 const int sizeOfEdge=1000001;
  6 
  7 int n, m, q;
  8 int w[sizeOfPoint];
  9 int f[sizeOfPoint], d[sizeOfPoint], s[sizeOfPoint];
 10 int num, idx[sizeOfPoint], top[sizeOfPoint], son[sizeOfPoint];
 11 inline char getch();
 12 inline int getint();
 13 inline void putint(int);
 14 
 15 struct edge {int point; edge * next;};
 16 edge memory[sizeOfEdge], * port=memory;
 17 edge * e[sizeOfPoint];
 18 inline edge * newedge(int, edge * );
 19 inline void link(int, int);
 20 
 21 int tot, stack[sizeOfPoint];
 22 edge * t[sizeOfPoint];
 23 inline void dfsTree();
 24 inline void dfsChain();
 25 
 26 int T[sizeOfPoint<<2];
 27 inline void build();
 28 inline void updateItem(int, int);
 29 inline int querySegment(int, int);
 30 
 31 inline void swap(int & , int & );
 32 inline int queryChain(int, int);
 33 
 34 int main()
 35 {
 36     char ch;
 37     int u, v;
 38 
 39     n=getint();
 40     for (int i=1;i<=n;i++)
 41         w[i]=getint();
 42     for (int i=1;i<n;i++)
 43     {
 44         int u=getint(), v=getint();
 45         link(u, v);
 46     }
 47 
 48     dfsTree();
 49     dfsChain();
 50     build();
 51 
 52     q=getint();
 53     for (int i=1;i<=q;i++)
 54     {
 55         ch=getch(), u=getint(), v=getint();
 56 
 57         if (ch=='Q') putint(queryChain(u, v));
 58         else updateItem(idx[u], v);
 59     }
 60 
 61     return 0;
 62 }
 63 inline char getch()
 64 {
 65     register char ch;
 66     do ch=getchar(); while (ch!='Q' && ch!='C');
 67     return ch;
 68 }
 69 inline int getint()
 70 {
 71     register int num=0;
 72     register char ch;
 73     do ch=getchar(); while (ch<'0' || ch>'9');
 74     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 75     return num;
 76 }
 77 inline void putint(int num)
 78 {
 79     if (num>0) putchar('Y'), putchar('e'), putchar('s');
 80     else putchar('N'), putchar('o');
 81     putchar('
');
 82 }
 83 inline edge * newedge(int point, edge * next)
 84 {
 85     edge * ret=port++;
 86     ret->point=point; ret->next=next;
 87     return ret;
 88 }
 89 inline void link(int u, int v)
 90 {
 91     e[u]=newedge(v, e[u]); e[v]=newedge(u, e[v]);
 92 }
 93 inline void dfsTree()
 94 {
 95     int u;
 96 
 97     memcpy(t, e, sizeof(e));
 98     memset(d, 0xFF, sizeof(d)); d[1]=0;
 99     s[1]=1;
100     for (stack[++tot]=1;tot; )
101     {
102         u=stack[tot];
103 
104         edge *& i=t[u];
105         for ( ;i && d[i->point]>=0;i=i->next);
106         if (i)
107         {
108             stack[++tot]=i->point;
109             f[i->point]=u;
110             d[i->point]=d[u]+1;
111             s[i->point]=1;
112         }
113         else
114         {
115             if (!f[u]) break;
116             s[f[u]]+=s[u];
117             if (s[u]>s[son[f[u]]])
118                 son[f[u]]=u;
119             tot--;
120         }
121     }
122 }
123 inline void dfsChain()
124 {
125     int u;
126 
127     memcpy(t, e, sizeof(e));
128     idx[1]=num=1; top[1]=1;
129     for (stack[++tot]=1;tot; )
130     {
131         u=stack[tot];
132         if (son[u] && !idx[son[u]])
133         {
134             stack[++tot]=son[u];
135             idx[son[u]]=++num;
136             top[son[u]]=top[u];
137             continue;
138         }
139 
140         edge *& i=t[u];
141         for ( ;i && idx[i->point];i=i->next);
142         if (i)
143         {
144             stack[++tot]=i->point;
145             idx[i->point]=++num;
146             top[i->point]=i->point;
147         }
148         else
149         {
150             if (!f[u]) break;
151             tot--;
152         }
153     }
154 }
155 inline void build()
156 {
157     for (m=1;m<n+2;m<<=1);
158     for (int i=1;i<=n;i++) T[idx[i]+m]=w[i];
159     for (int i=m;i>=1;i--) T[i]=T[i<<1]^T[i<<1|1];
160 }
161 inline void updateItem(int i, int t)
162 {
163     for (T[i+=m]=t, i>>=1;i;i>>=1) T[i]=T[i<<1]^T[i<<1|1];
164 }
165 inline int querySegment(int l, int r)
166 {
167     int sum=0;
168     for (l=l+m-1, r=r+m+1;l^r^1;l>>=1, r>>=1)
169     {
170         if (~l&1) sum^=T[l^1];
171         if ( r&1) sum^=T[r^1];
172     }
173     return sum;
174 }
175 inline void swap(int & u, int & v)
176 {
177     int t=u; u=v; v=t;
178 }
179 inline int queryChain(int u, int v)
180 {
181     int sum=0;
182     while (top[u]!=top[v])
183     {
184         if (d[top[u]]<d[top[v]]) swap(u, v);
185         sum^=querySegment(idx[top[u]], idx[u]);
186         u=f[top[u]];
187     }
188     if (d[u]>d[v]) swap(u, v);
189     sum^=querySegment(idx[u], idx[v]);
190     return sum;
191 }
1A 好评如潮
原文地址:https://www.cnblogs.com/dyllalala/p/4136149.html