激!QTREE系列

我现在才开始刷 QTREE 是不是太弱了?算了不管他……

QTREE: 树链剖分裸题(据说 lct 会超时……该说是真不愧有 spoj 的气息吗?)

  1 #include <cstdio>
  2 #include <cstring>
  3 const int sizeOfPoint=10001;
  4 const int sizeOfEdge=20002;
  5 const int sizeOfNode=40004;
  6 
  7 inline void swap(int & , int & );
  8 inline int max(int, int);
  9 inline char getch();
 10 inline int getint();
 11 inline void putint(int);
 12 
 13 struct edge {int index, point, dist; edge * next;};
 14 edge memory_edge[sizeOfEdge], * port_edge=memory_edge;
 15 inline edge * newedge(int, int, int, edge * );
 16 inline void link(int, int, int, int);
 17 
 18 struct node {int c; node * l, * r;};
 19 node memory_node[sizeOfNode], * port_node=memory_node;
 20 inline node * newnode();
 21 node * build(int, int);
 22 void update(node * , int, int, int, int);
 23 int query(node * , int, int, int, int);
 24 
 25 edge * e[sizeOfPoint];
 26 int d[sizeOfPoint], f[sizeOfPoint], s[sizeOfPoint];
 27 int num, idx[sizeOfPoint], son[sizeOfPoint], top[sizeOfPoint];
 28 void dfs(int);
 29 void divide(int, int);
 30 inline int query(int, int);
 31 
 32 int c, n;
 33 int a[sizeOfPoint], k[sizeOfPoint];
 34 node * t;
 35 inline void clear();
 36 
 37 int main()
 38 {
 39     for (c=getint();c;c--)
 40     {
 41         clear();
 42 
 43         n=getint();
 44         for (int i=1;i<n;i++)
 45         {
 46             int u=getint(), v=getint(), d=getint();
 47             link(i, u, v, d);
 48         }
 49         dfs(1);
 50         divide(1, 1);
 51 
 52         t=build(1, n);
 53         for (int i=1;i<=n;i++)
 54             update(t, 1, n, idx[i], a[i]);
 55 
 56         while (true)
 57         {
 58             char ch=getch();
 59             if (ch=='D') break;
 60             else if (ch=='Q')
 61             {
 62                 int u=getint(), v=getint();
 63                 putint(query(u, v));
 64             }
 65             else if (ch=='C')
 66             {
 67                 int u=getint(), v=getint();
 68                 a[k[u]]=v;
 69                 update(t, 1, n, idx[k[u]], v);
 70             }
 71         }
 72     }
 73 
 74     return 0;
 75 }
 76 
 77 inline void swap(int & x, int & y)
 78 {
 79     int t=x; x=y; y=t;
 80 }
 81 inline int max(int x, int y)
 82 {
 83     return x>y?x:y;
 84 }
 85 inline char getch()
 86 {
 87     register char ch;
 88     do ch=getchar(); while (ch!='Q' && ch!='C' && ch!='D');
 89     return ch;
 90 }
 91 inline int getint()
 92 {
 93     register int num=0;
 94     register char ch=0, last;
 95     do last=ch, ch=getchar(); while (ch<'0' || ch>'9');
 96     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 97     if (last=='-') num=-num;
 98     return num;
 99 }
100 inline void putint(int num)
101 {
102     char stack[11];
103     register int top=0;
104     if (num<0) putchar('-'), num=-num;
105     if (num==0) stack[top=1]='0';
106     for ( ;num;num/=10) stack[++top]=num%10+'0';
107     for ( ;top;top--) putchar(stack[top]);
108     putchar('
');
109 }
110 
111 inline edge * newedge(int index, int point, int dist, edge * next)
112 {
113     edge * ret=port_edge++;
114     ret->index=index; ret->point=point; ret->dist=dist; ret->next=next;
115     return ret;
116 }
117 inline void link(int i, int u, int v, int d)
118 {
119     e[u]=newedge(i, v, d, e[u]);
120     e[v]=newedge(i, u, d, e[v]);
121 }
122 
123 inline node * newnode()
124 {
125     node * ret=port_node++;
126     ret->c=0; ret->l=NULL; ret->r=NULL;
127     return ret;
128 }
129 node * build(int l, int r)
130 {
131     node * t=newnode();
132 
133     if (l==r)
134         return t;
135 
136     int m=(l+r)>>1;
137     t->l=build(l, m);
138     t->r=build(m+1, r);
139     t->c=max(t->l->c, t->r->c);
140 
141     return t;
142 }
143 void update(node * t, int l, int r, int k, int v)
144 {
145     if (l==r)
146     {
147         t->c=v;
148         return ;
149     }
150 
151     int m=(l+r)>>1;
152     if (k<=m) update(t->l, l, m, k, v);
153     else update(t->r, m+1, r, k, v);
154     t->c=max(t->l->c, t->r->c);
155 }
156 int query(node * t, int l, int r, int ql, int qr)
157 {
158     if (l==ql && r==qr)
159         return t->c;
160 
161     int m=(l+r)>>1;
162     if (qr<=m) return query(t->l, l, m, ql, qr);
163     else if (ql>m) return query(t->r, m+1, r, ql, qr);
164     else return max(query(t->l, l, m, ql, m), query(t->r, m+1, r, m+1, qr));
165 }
166 
167 void dfs(int u)
168 {
169     s[u]=1;
170     for (edge * i=e[u];i;i=i->next) if (f[i->point]==-1)
171     {
172         a[i->point]=i->dist; k[i->index]=i->point;
173         f[i->point]=u; d[i->point]=d[u]+1;
174         dfs(i->point);
175         if (s[i->point]>s[son[u]])
176             son[u]=i->point;
177     }
178 }
179 void divide(int u, int top_u)
180 {
181     idx[u]=++num; top[u]=top_u;
182     if (son[u]) divide(son[u], top_u);
183     for (edge * i=e[u];i;i=i->next) if (!idx[i->point])
184         divide(i->point, i->point);
185 }
186 inline int query(int u, int v)
187 {
188     int ret=0;
189 
190     while (top[u]!=top[v])
191     {
192         if (d[top[u]]<d[top[v]]) swap(u, v);
193         ret=max(ret, query(t, 1, n, idx[top[u]], idx[u]));
194         u=f[top[u]];
195     }
196     if (u==v) return ret;
197 
198     if (d[u]>d[v]) swap(u, v);
199     ret=max(ret, query(t, 1, n, idx[u]+1, idx[v]));
200 
201     return ret;
202 }
203 
204 inline void clear()
205 {
206     memset(a, 0, sizeof(a));
207     memset(k, 0, sizeof(k));
208     port_edge=memory_edge; port_node=memory_node;
209     memset(e, 0, sizeof(e));
210     memset(s, 0, sizeof(s));
211     memset(f, 0xFF, sizeof(f)); f[1]=0;
212     memset(d, 0, sizeof(d));
213     num=0;
214     memset(idx, 0, sizeof(idx));
215     memset(son, 0, sizeof(son));
216     memset(top, 0, sizeof(top));
217 }
QTREE

QTREE2: 因为没有修改操作,机智地用了倍增,在 spoj 上貌似挺快的……

  1 #include <cstdio>
  2 #include <cstring>
  3 const int sizeOfPoint=10001;
  4 const int sizeOfEdge=20002;
  5 
  6 inline void swap(int & , int & );
  7 inline int lg(int);
  8 inline int lowbit(int);
  9 inline char getch();
 10 inline int getint();
 11 inline void putint(int);
 12 
 13 struct edge {int point, dist; edge * next;};
 14 edge memory[sizeOfEdge], * port=memory;
 15 inline edge * newedge(int, int, edge * );
 16 inline void link(int, int, int);
 17 
 18 int c, n;
 19 edge * e[sizeOfPoint];
 20 int a[sizeOfPoint], s[sizeOfPoint];
 21 int f[20][sizeOfPoint], d[sizeOfPoint];
 22 inline void clear();
 23 void dfs(int);
 24 inline int anc(int, int);
 25 inline int lca(int, int);
 26 
 27 int main()
 28 {
 29     for (c=getint();c;c--)
 30     {
 31         clear();
 32 
 33         n=getint();
 34         for (int i=1;i<n;i++)
 35         {
 36             int u=getint(), v=getint(), d=getint();
 37             link(u, v, d);
 38         }
 39         dfs(1);
 40 
 41         while (true)
 42         {
 43             char ch=getch();
 44             if (ch=='O') break;
 45             else if (ch=='I')
 46             {
 47                 int u=getint(), v=getint(), l=lca(u, v);
 48 
 49                 putint(s[u]+s[v]-(s[l]<<1));
 50             }
 51             else
 52             {
 53                 int u=getint(), v=getint(), k=getint(), l=lca(u, v), s=(d[u]-d[l])+(d[v]-d[l])+1;
 54 
 55                 if (d[u]-d[l]>=k)
 56                     putint(anc(u, k-1));
 57                 else
 58                     putint(anc(v, s-k));
 59             }
 60         }
 61     }
 62 
 63     return 0;
 64 }
 65 
 66 inline void swap(int & x, int & y)
 67 {
 68     int t=x; x=y; y=t;
 69 }
 70 inline int lg(int x)
 71 {
 72     return x?31-__builtin_clz(x):0;
 73 }
 74 inline int lowbit(int x)
 75 {
 76     return x & -x;
 77 }
 78 inline char getch()
 79 {
 80     register char ch;
 81     do ch=getchar(); while (ch!='D' && ch!='K');
 82     if (ch=='D') ch=getchar();
 83     return ch;
 84 }
 85 inline int getint()
 86 {
 87     register int num=0;
 88     register char ch=0, last;
 89     do last=ch, ch=getchar(); while (ch<'0' || ch>'9');
 90     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 91     if (last=='-') num=-num;
 92     return num;
 93 }
 94 inline void putint(int num)
 95 {
 96     char stack[11];
 97     register int top=0;
 98     if (num==0) stack[top=1]='0';
 99     if (num<0) putchar('-'), num=-num;
100     for ( ;num;num/=10) stack[++top]=num%10+'0';
101     for ( ;top;top--) putchar(stack[top]);
102     putchar('
');
103 }
104 
105 inline edge * newedge(int point, int dist, edge * next)
106 {
107     edge * ret=port++;
108     ret->point=point; ret->dist=dist; ret->next=next;
109     return ret;
110 }
111 inline void link(int u, int v, int d)
112 {
113     e[u]=newedge(v, d, e[u]);
114     e[v]=newedge(u, d, e[v]);
115 }
116 
117 inline void clear()
118 {
119     port=memory;
120     memset(e, 0, sizeof(e));
121     memset(f, 0, sizeof(f));
122     memset(d, 0xFF, sizeof(d)); d[1]=0;
123     memset(a, 0, sizeof(a));
124     memset(s, 0, sizeof(s));
125 }
126 void dfs(int u)
127 {
128     if (d[u]>1)
129     {
130         int _lim=lg(d[u]);
131         for (int i=1;i<=_lim;i++)
132             f[i][u]=f[i-1][f[i-1][u]];
133     }
134 
135     for (edge * i=e[u];i;i=i->next) if (d[i->point]==-1)
136     {
137         f[0][i->point]=u;
138         d[i->point]=d[u]+1;
139         a[i->point]=i->dist;
140         s[i->point]=s[u]+i->dist;
141         dfs(i->point);
142     }
143 }
144 inline int anc(int u, int s)
145 {
146     for ( ;s;s-=lowbit(s))
147         u=f[__builtin_ctz(s)][u];
148     return u;
149 }
150 inline int lca(int u, int v)
151 {
152     if (d[u]<d[v]) swap(u, v);
153     u=anc(u, d[u]-d[v]);
154     if (u==v) return u;
155 
156     for (int i=19;i>=0;i--)
157         if (f[i][u]!=f[i][v])
158             u=f[i][u],
159             v=f[i][v];
160 
161     return f[0][u];
162 }
QTREE2

QTREE4:

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 const int sizeOfPoint=100001;
  5 const int sizeOfEdge=200002;
  6 const int sizeOfSeg=2000002;
  7 
  8 inline int lg(int);
  9 inline int rev(int);
 10 inline int getint();
 11 inline void putint(int);
 12 
 13 struct edge
 14 {
 15     int point;
 16     edge * next;
 17 };
 18 edge memoryOfEdge[sizeOfEdge], * portOfEdge=memoryOfEdge;
 19 inline edge * newedge(int, edge * );
 20 inline void link(int, int);
 21 
 22 struct seg
 23 {
 24     bool b;
 25     int f;
 26     seg * l, * r;
 27     inline seg();
 28     inline void pushdown();
 29     inline void maintain();
 30 };
 31 seg * null=new seg();
 32 seg memoryOfSeg[sizeOfSeg], * portOfSeg=memoryOfSeg;
 33 inline void swap(seg *& , seg *& );
 34 seg * newseg(seg * =null);
 35 seg * insert(seg * , int, int);
 36 inline int query(seg * );
 37 
 38 int n, m;
 39 bool c[sizeOfPoint];
 40 int f[sizeOfPoint];
 41 int sg[sizeOfPoint], s[sizeOfPoint];
 42 int dp[sizeOfPoint];
 43 int tot, ans[sizeOfPoint];
 44 edge * e[sizeOfPoint];
 45 seg * t[sizeOfPoint];
 46 inline void bfs();
 47 
 48 int main()
 49 {
 50     n=getint(); m=lg(n);
 51     for (int i=1;i<=n;i++)
 52         c[i]=getint();
 53     for (int i=1;i<n;i++)
 54     {
 55         int u=getint(), v=getint();
 56         link(u, v);
 57     }
 58     bfs();
 59 
 60     if (!tot) ans[tot++]=-1;
 61     std::sort(ans, ans+tot);
 62     for (int i=0;i<tot;i++)
 63         putint(ans[i]);
 64 
 65     return 0;
 66 }
 67 
 68 inline int lg(int x)
 69 {
 70     return 32-__builtin_clz(x);
 71 }
 72 inline int rev(int x)
 73 {
 74     int ret=0;
 75     for (int i=0;i<m;i++)
 76     {
 77         ret=(ret<<1)|(x&1);
 78         x>>=1;
 79     }
 80     return ret;
 81 }
 82 inline int getint()
 83 {
 84     register int num=0;
 85     register char ch;
 86     do ch=getchar(); while (ch<'0' || ch>'9');
 87     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 88     return num;
 89 }
 90 inline void putint(int num)
 91 {
 92     char stack[11];
 93     register int top=0;
 94     if (num==0) stack[top=1]='0';
 95     if (num<0) putchar('-'), num=-num;
 96     for ( ;num;num/=10) stack[++top]=num%10+'0';
 97     for ( ;top;top--) putchar(stack[top]);
 98     putchar('
');
 99 }
100 
101 inline edge * newedge(int point, edge * next)
102 {
103     edge * ret=portOfEdge++;
104     ret->point=point; ret->next=next;
105     return ret;
106 }
107 inline void link(int u, int v)
108 {
109     e[u]=newedge(v, e[u]);
110     e[v]=newedge(u, e[v]);
111 }
112 
113 inline seg::seg()
114 {
115     b=false;
116     f=0;
117     l=r=this;
118 }
119 inline void seg::pushdown()
120 {
121     if (f)
122     {
123         if (f&1)
124         {
125             swap(l, r);
126             l->f^=f>>1, r->f^=f>>1;
127         }
128         f=0;
129     }
130 }
131 inline void seg::maintain()
132 {
133     b=l->b&r->b;
134 }
135 inline void swap(seg *& a, seg *& b)
136 {
137     seg * t=a; a=b; b=t;
138 }
139 inline seg * newseg(seg * t)
140 {
141     seg * newt=portOfSeg++;
142     *newt=*t;
143     if (t==null) newt->b=false, newt->f=0;
144     return newt;
145 }
146 seg * insert(seg * t, int k, int d)
147 {
148     t=newseg(t);
149     if (d==0) return t->b=true, t;
150     t->pushdown();
151     if (k&1) t->r=insert(t->r, k>>1, d-1);
152     else t->l=insert(t->l, k>>1, d-1);
153     t->maintain();
154     return t;
155 }
156 seg * merge(seg * a, seg * b)
157 {
158     if (a==null || b->b) return b;
159     if (b==null || a->b) return a;
160     a->pushdown(), b->pushdown();
161     seg * t=newseg();
162     t->l=merge(a->l, b->l);
163     t->r=merge(a->r, b->r);
164     t->maintain();
165     return t;
166 }
167 inline int query(seg * t)
168 {
169     int ret=0;
170     for (int i=0;i<m;i++)
171     {
172         t->pushdown();
173         if (t->l->b)
174         {
175             ret=ret<<1|1;
176             t=t->r;
177         }
178         else
179         {
180             ret=ret<<1;
181             t=t->l;
182         }
183     }
184     return ret;
185 }
186 
187 inline void bfs()
188 {
189     static int q[sizeOfPoint];
190     int l=0, r=0;
191     memset(f, 0xFF, sizeof(f)); f[1]=0;
192     for (q[r++]=1;l<r;l++)
193     {
194         int u=q[l];
195         for (edge * i=e[u];i;i=i->next) if (f[i->point]==-1)
196         {
197             f[i->point]=u;
198             q[r++]=i->point;
199         }
200     }
201     for (int h=r-1;h>=0;h--)
202     {
203         int u=q[h];
204         t[u]=newseg();
205         for (edge * i=e[u];i;i=i->next) if (f[i->point]==u)
206             s[u]^=sg[i->point];
207         for (edge * i=e[u];i;i=i->next) if (f[i->point]==u)
208         {
209             t[i->point]->f^=rev(s[u]^sg[i->point]);
210             t[u]=merge(t[u], t[i->point]);
211         }
212         if (!c[u])
213             t[u]=insert(t[u], rev(s[u]), m);
214         sg[u]=query(t[u]);
215     }
216     for (int h=0;h<r;h++)
217     {
218         int u=q[h];
219         if (!c[u] && dp[u]==s[u]) ans[tot++]=u;
220         for (edge * i=e[u];i;i=i->next) if (f[i->point]==u)
221             dp[i->point]=dp[u]^s[u]^sg[i->point];
222     }
223 }
View Code
  1 #include <cstdio>
  2 #include <cstring>
  3 #include <vector>
  4 #include <queue>
  5 typedef std::priority_queue<struct pair, std::vector<struct pair>, std::greater<struct pair> > heap;
  6 const int sizeOfPoint=100001;
  7 const int sizeOfEdge=200002;
  8 const int sizeOfSeg=400004;
  9 
 10 inline int min(int, int);
 11 inline int getint();
 12 inline void putint(int);
 13 
 14 struct edge
 15 {
 16     int point;
 17     edge * next;
 18 };
 19 edge memoryOfEdge[sizeOfEdge], * portOfEdge=memoryOfEdge;
 20 inline edge * newedge(int, edge * );
 21 inline void link(int, int);
 22 
 23 struct pair
 24 {
 25     int w, u, t;
 26     inline pair(int, int, int);
 27 };
 28 inline bool operator > (pair, pair);
 29 
 30 struct node
 31 {
 32     int lmin, rmin, sum;
 33     inline node(int=0, int=0, int=0);
 34 };
 35 inline node merge(node, node);
 36 
 37 struct seg
 38 {
 39     node d;
 40     seg * l, * r;
 41     inline void maintain();
 42 };
 43 seg memoryOfSeg[sizeOfSeg], * portOfSeg=memoryOfSeg;
 44 inline seg * newseg();
 45 seg * build(int, int);
 46 void update(seg * , int, int, int);
 47 node query(seg * , int, int, int, int);
 48 
 49 int n, m;
 50 int l[sizeOfPoint], r[sizeOfPoint], b[sizeOfPoint];
 51 bool c[sizeOfPoint];
 52 edge * e[sizeOfPoint];
 53 int d[sizeOfPoint], s[sizeOfPoint], f[sizeOfPoint];
 54 int tmp, idx[sizeOfPoint], son[sizeOfPoint], top[sizeOfPoint];
 55 heap h[sizeOfPoint];
 56 int w[sizeOfPoint];
 57 inline void dfs();
 58 inline void getw(int);
 59 
 60 int main()
 61 {
 62     n=getint();
 63     for (int i=1;i<=n;i++)
 64     {
 65         int u=getint(), v=getint();
 66         link(u, v);
 67     }
 68     dfs();
 69 
 70     return 0;
 71 }
 72 
 73 inline int min(int x, int y)
 74 {
 75     return x<y?x:y;
 76 }
 77 inline int getint()
 78 {
 79     register int num=0;
 80     register char ch;
 81     do ch=getchar(); while (ch<'0' || ch>'9');
 82     do num=num*10+ch-'0', ch=getchar(); while (ch>='0' && ch<='9');
 83     return num;
 84 }
 85 inline void putint(int num)
 86 {
 87     char stack[11];
 88     register int top=0;
 89     if (num==0) stack[top=1]='0';
 90     if (num<0) putchar('-'), num=-num;
 91     for ( ;num;num/=10) stack[++top]=num%10+'0';
 92     for ( ;top;top--) putchar(stack[top]);
 93     putchar('
');
 94 }
 95 
 96 inline edge * newedge(int point, edge * next)
 97 {
 98     edge * ret=portOfEdge++;
 99     ret->point=point; ret->next=next;
100     return ret;
101 }
102 inline void link(int u, int v)
103 {
104     e[u]=newedge(v, e[u]);
105     e[v]=newedge(u, e[v]);
106 }
107 
108 inline pair::pair(int _w, int _u, int _t)
109 {
110     w=_w; u=_u; t=_t;
111 }
112 inline bool operator > (pair a, pair b)
113 {
114     return a.w>b.w;
115 }
116 
117 inline node::node(int _lmin, int _rmin, int _sum)
118 {
119     lmin=_lmin; rmin=_rmin; sum=_sum;
120 }
121 inline node merge(node a, node b)
122 {
123     node c;
124     c.lmin=min(a.lmin, a.sum+1+b.lmin);
125     c.rmin=min(b.rmin, a.rmin+1+b.sum);
126     c.sum=a.sum+1+b.sum;
127     return c;
128 }
129 
130 inline void seg::maintain()
131 {
132     d=merge(l->d, r->d);
133 }
134 inline seg * newseg()
135 {
136     return portOfSeg++;
137 }
138 seg * build(int l, int r)
139 {
140     seg * t=newseg();
141     int m=(l+r)>>1;
142 
143     if (l==r)
144     {
145         t->d.lmin=t->d.rmin=w[m];
146         t->d.sum=0;
147     }
148     else
149     {
150         t->l=build(l, m);
151         t->r=build(m+1, r);
152         t->maintain();
153     }
154 
155     return t;
156 }
157 void update(seg * t, int l, int r, int k)
158 {
159     int m=(l+r)>>1;
160 
161     if (l==r)
162         t->d.lmin=t->d.rmin=w[m];
163     else
164     {
165         if (k<=m) update(t->l, l, m, k);
166         else update(t->r, m+1, r, k);
167         t->maintain();
168     }
169 }
170 node query(seg * t, int l, int r, int ql, int qr)
171 {
172     if (l==ql && r==qr) return t->d;
173     int m=(l+r)>>1;
174     if (qr<=m) return query(t->l, l, m, ql, qr);
175     else if (ql>m) return query(t->r, m+1, r, ql, qr);
176     else return merge(query(t->l, l, m, ql, m), query(t->r, m+1, r, m+1, qr));
177 }
178 
179 inline void dfs()
180 {
181     static edge * t[sizeOfPoint];
182     memmove(t, e, sizeof(e));
183 }
QTREE5
原文地址:https://www.cnblogs.com/dyllalala/p/4181193.html