关键词：
3307: 雨天的尾巴
模板题。
简单题调不过最好的方法是重构代码或者放一天然后重构代码。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define For(i,a,b) for(int i=(a);i<=(b);i++)
13 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
14 const int N=100007;
15 typedef long long LL;
16 typedef double db;
17 using namespace std;
18 int n,m,SZ,xx[N],yy[N],zz[N],ls[N];
19
20 template<typename T> void read(T &x)
21 char ch=getchar(); x=0; T f=1;
22 while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
23 if(ch==‘-‘) f=-1,ch=getchar();
24 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘; x*=f;
25
26
27 int ecnt,fir[N],nxt[N<<1],to[N<<1];
28 void add(int u,int v)
29 nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
30 nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;
31
32
33 int f[N][20],R[N];
34 void dfs(int x,int fa)
35 f[x][0]=fa;
36 R[x]=R[fa]+1;
37 For(i,1,19) f[x][i]=f[f[x][i-1]][i-1];
38 for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa)
39 dfs(to[i],x);
40
41
42 int lca(int x,int y)
43 if(R[x]<R[y]) swap(x,y);
44 Rep(i,19,0) if(R[f[x][i]]>=R[y])
45 x=f[x][i];
46 if(x==y) return x;
47 Rep(i,19,0) if(f[x][i]!=f[y][i])
48 x=f[x][i],y=f[y][i];
49 return f[x][0];
50
51
52 vector<int>vc[N];
53 int tot,ch[N*50][2],rt[N],id[N*50];
54 LL sg[N*50];
55 #define lc ch[x][0]
56 #define rc ch[x][1]
57 #define mid ((l+r)>>1)
58 void update(int x)
59 if(sg[lc]>=sg[rc]) sg[x]=sg[lc],id[x]=id[lc];
60 else sg[x]=sg[rc],id[x]=id[rc];
61
62
63 void add(int &x,int l,int r,int pos,int v)
64 if(!x) x=++tot;
65 if(l==r) sg[x]+=v; id[x]=l; return;
66 if(pos<=mid) add(lc,l,mid,pos,v);
67 else add(rc,mid+1,r,pos,v);
68 update(x);
69
70
71 void merge(int &x,int y,int l,int r)
72 if(!(x*y)) x=(x^y); return;
73 if(l==r) sg[x]=sg[x]+sg[y];
74 else
75 merge(lc,ch[y][0],l,mid);
76 merge(rc,ch[y][1],mid+1,r);
77 update(x);
78
79
80
81 int ans[N];
82 void dfs2(int x,int fa)
83 for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa)
84 dfs2(to[i],x);
85 merge(rt[x],rt[to[i]],1,SZ);
86
87 int up=vc[x].size();
88 For(i,0,up-1)
89 int w=vc[x][i];
90 add(rt[x],1,SZ,abs(w),w>0?1:-1);
91
92 ans[x]=id[rt[x]];
93
94
95 //#define DEBUG
96 int main()
97 #ifdef DEBUG
98 freopen("1.in","r",stdin);
99 //freopen(".out","w",stdout);
100 #endif
101 read(n); read(m);
102 For(i,1,n-1)
103 int x,y;
104 read(x); read(y);
105 add(x,y);
106
107 For(i,1,m)
108 read(xx[i]); read(yy[i]); read(zz[i]);
109 ls[i]=zz[i];
110
111 dfs(1,0);
112 sort(ls+1,ls+m+1);
113 SZ=unique(ls+1,ls+m+1)-(ls+1);
114 For(i,1,m) zz[i]=lower_bound(ls+1,ls+SZ+1,zz[i])-ls;
115 For(i,1,m)
116 int x=xx[i],y=yy[i],w=zz[i];
117 int z=lca(x,y);
118 vc[x].push_back(w);
119 vc[y].push_back(w);
120 vc[z].push_back(-w);
121 vc[f[z][0]].push_back(-w);
122
123 dfs2(1,0);
124 For(i,1,n) printf("%d\n",ls[ans[i]]);
125 return 0;
126
2212: [Poi2011]Tree Rotations
模板题。或许可以set+启发式合并水过去。
线段树合并，合并的时候可以算出两种方式的逆序对数，取小的即可。
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define For(i,a,b) for(int i=(a);i<=(b);i++)
13 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
14 const int N=400007;
15 typedef long long LL;
16 typedef double db;
17 using namespace std;
18 int n;
19
20 template<typename T> void read(T &x)
21 char ch=getchar(); x=0; T f=1;
22 while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
23 if(ch==‘-‘) f=-1,ch=getchar();
24 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘; x*=f;
25
26
27 int tot,ch[N*20][2],rt[N],sg[N*20],leaf;
28 #define lc ch[x][0]
29 #define rc ch[x][1]
30 #define mid ((l+r)>>1)
31 void update(int x) sg[x]=sg[lc]+sg[rc];
32
33 void add(int &x,int l,int r,int pos,int v)
34 if(!x) x=++tot;
35 if(l==r) sg[x]+=v; return;
36 if(pos<=mid) add(lc,l,mid,pos,v);
37 else add(rc,mid+1,r,pos,v);
38 update(x);
39
40
41 LL lans,rans;
42 void merge(int &x,int y,int l,int r)
43 if(!(x*y)) x=(x^y); return;
44 if(l==r) sg[x]=sg[x]+sg[y];
45 else
46 lans=lans+(LL)sg[rc]*sg[ch[y][0]];
47 rans=rans+(LL)sg[ch[y][1]]*sg[lc];
48 merge(lc,ch[y][0],l,mid);
49 merge(rc,ch[y][1],mid+1,r);
50 update(x);
51
52
53
54 int id,lson[N],rson[N],v[N],RT;
55 int read_a_tree()
56 int x=++id; read(v[x]);
57 if(v[x]==0)
58 lson[x]=read_a_tree();
59 rson[x]=read_a_tree();
60
61 else leaf++;
62 return x;
63
64
65 LL ans;
66 void dfs(int x)
67 if(v[x]) add(rt[x],1,leaf,v[x],1);
68 else
69 dfs(lson[x]);
70 dfs(rson[x]);
71 lans=rans=0;
72 merge(rt[lson[x]],rt[rson[x]],1,leaf);
73 rt[x]=rt[lson[x]];
74 ans+=min(lans,rans);
75
76
77
78 //#define DEBUG
79 int main()
80 #ifdef DEBUG
81 freopen("1.in","r",stdin);
82 //freopen(".out","w",stdout);
83 #endif
84 read(n);
85 RT=read_a_tree();
86 dfs(RT);
87 printf("%lld\n",ans);
88 return 0;
89
4552: [Tjoi2016&Heoi2016]排序
一种比较好写的做法是，二分答案，把小于它的设为-1,大于它的设为1，再用线段树搞。复杂度是两个log的，可以过掉这道题。
另一种复杂度更优秀，适用范围更广的做法是线段树分裂合并。
区间排序，把区间左右超过范围的部分分裂出去，一段区间合并即可。
具体来说，另开一棵不用动态开点的线段树存每个点所在线段树维护区间的左右端点，再用数组存每个左端点对应的右端点，每棵线段树的根节点挂在左端点上，升序降序的标记也打在左端点上。
这样的时间复杂度可以证明是nlogn的。
感谢uoj用户群的大佬的证明：
势能分析。势能函数为总结点个数。初始节点数nlogn，由于操作增加的节点数qlogn,合并时额外x的时间花费一定会同时删去x个节点，所以总时间花费不超过(n+q)logn
感谢Cai大佬为我这样无比智障的蒟蒻的解释：
就是你最开始线段树上是nlogn个节点，加上每次分裂得到的qlogn个节点，所以节点总数不会超过(n+q)logn，每次线段树合并所需要花费的代价就是两个课都有的公共节点部分，合并完之后这些节点就没了(在新树上就是一个节点)，而你总共只有(n+q)logn个节点，所以时间复杂度为(n+q)logn
1 //Achen
2 #include<algorithm>
3 #include<iostream>
4 #include<cstring>
5 #include<cstdlib>
6 #include<vector>
7 #include<cstdio>
8 #include<queue>
9 #include<cmath>
10 #include<set>
11 #include<map>
12 #define For(i,a,b) for(int i=(a);i<=(b);i++)
13 #define Rep(i,a,b) for(int i=(a);i>=(b);i--)
14 const int N=1e5+7;
15 typedef long long LL;
16 typedef double db;
17 using namespace std;
18 int n,m,rt[N],lz[N<<2],flip[N],nx[N];
19
20 template<typename T> void read(T &x)
21 char ch=getchar(); x=0; T f=1;
22 while(ch!=‘-‘&&(ch<‘0‘||ch>‘9‘)) ch=getchar();
23 if(ch==‘-‘) f=-1,ch=getchar();
24 for(;ch>=‘0‘&&ch<=‘9‘;ch=getchar()) x=x*10+ch-‘0‘; x*=f;
25
26
27 struct node int l,r; sg[N<<2];
28 #define ls x<<1
29 #define rs ((x<<1)|1)
30 #define mid ((l+r)>>1)
31 void build(int x,int l,int r)
32 if(l==r) sg[x].l=l; sg[x].r=r; return;
33 build(ls,l,mid); build(rs,mid+1,r);
34
35
36 void down(int x,int l,int r)
37 if(!lz[x]||l==r) return;
38 sg[ls].l=sg[x].l,sg[ls].r=sg[x].r;
39 sg[rs].l=sg[x].l,sg[rs].r=sg[x].r;
40 lz[x]=0; lz[ls]=lz[rs]=1; return;
41
42
43 void change(int x,int l,int r,int ql,int qr,int ll,int rr)
44 if(l>=ql&&r<=qr)
45 sg[x].l=ll; sg[x].r=rr; lz[x]=1; return;
46
47 down(x,l,r);
48 if(ql<=mid) change(ls,l,mid,ql,qr,ll,rr);
49 if(qr>mid) change(rs,mid+1,r,ql,qr,ll,rr);
50
51
52 node qry(int x,int l,int r,int pos)
53 if(l==r) return sg[x];
54 down(x,l,r);
55 if(pos<=mid) return qry(ls,l,mid,pos);
56 else return qry(rs,mid+1,r,pos);
57
58
59 int tot,ch[N*50][2],sum[N*50];
60 #define lc ch[x][0]
61 #define rc ch[x][1]
62 void upd(int x) sum[x]=sum[lc]+sum[rc];
63
64 void update(int &x,int l,int r,int pos,int v)
65 if(!x) x=++tot;
66 if(l==r) sum[x]+=v; return;
67 if(pos<=mid) update(lc,l,mid,pos,v);
68 else update(rc,mid+1,r,pos,v);
69 upd(x);
70
71
72 void merge(int &x,int y,int l,int r)
73 if(!(x*y)) x=(x^y); return;
74 if(l==r) sum[x]+=sum[y]; return;
75 merge(lc,ch[y][0],l,mid);
76 merge(rc,ch[y][1],mid+1,r);
77 upd(x);
78
79
80 node split(int x,int l,int r,int k)
81 int z=++tot;
82 if(sum[lc]==k)
83 ch[z][0]=lc; lc=0;
84
85 else if(sum[lc]<k)
86 node tp=split(rc,mid+1,r,k-sum[lc]);
87 ch[x][1]=tp.l; ch[z][1]=tp.r; swap(x,z);
88
89 else
90 node tp=split(lc,l,mid,k);
91 ch[x][0]=tp.r; ch[z][0]=tp.l;
92
93 upd(x); upd(z);
94 return (node)z,x;
95
96
97 int find(int x,int l,int r,int pos)
98 if(l==r) return l;
99 if(sum[lc]>=pos) return find(lc,l,mid,pos);
100 if(sum[lc]<pos) return find(rc,mid+1,r,pos-sum[lc]);
101
102
103 //#define DEBUG
104 int main()
105 #ifdef DEBUG
106 freopen("std.in","r",stdin);
107 //freopen(".out","w",stdout);
108 #endif
109 read(n); read(m);
110 For(i,1,n) nx[i]=i,rt[i]=++tot;
111 build(1,1,n);
112 For(i,1,n)
113 int x; read(x);
114 update(rt[i],1,n,x,1);
115
116 For(i,1,m)
117 int l,r,o,x;
118 read(o); read(l); read(r);
119 node tl=qry(1,1,n,l);
120 //zhu yi qu fen tp.l tp.r he tl.l tl.r
121 if(tl.l<l)
122 x=rt[tl.l];
123 if(flip[tl.l])
124 node tp=split(x,1,n,tl.r-tl.l+1-(l-tl.l));
125 rt[tl.l]=tp.r; rt[l]=tp.l;
126 flip[tl.l]=flip[l]=1;
127
128 else
129 node tp=split(x,1,n,l-tl.l);
130 rt[tl.l]=tp.l; rt[l]=tp.r;
131 flip[tl.l]=flip[l]=0; //zheng biao ji ye yao xia fang
132
133 nx[l]=nx[tl.l]; nx[tl.l]=l-1;
134 change(1,1,n,l,nx[l],l,nx[l]); //fen lie hou ye yao xiu gai zhe ke xian duan shu
135 change(1,1,n,tl.l,nx[tl.l],tl.l,nx[tl.l]);
136
137 node tr=qry(1,1,n,r);
138 if(tr.r>r)
139 x=rt[tr.l];
140 if(flip[tr.l])
141 node tp=split(x,1,n,tr.r-r);
142 rt[tr.l]=tp.r; rt[r+1]=tp.l;
143 flip[tr.l]=flip[r+1]=1;
144
145 else
146 node tp=split(x,1,n,(tr.r-tr.l+1)-(tr.r-r));
147 rt[tr.l]=tp.l; rt[r+1]=tp.r;
148 flip[tr.l]=flip[r+1]=0;
149
150 nx[r+1]=nx[tr.l]; nx[tr.l]=r;
151 change(1,1,n,r+1,nx[r+1],r+1,nx[r+1]);
152 change(1,1,n,tr.l,nx[tr.l],tr.l,nx[tr.l]);
153
154 change(1,1,n,l,r,l,r);
155 x=l;
156 while(nx[x]+1<=r)
157 merge(rt[l],rt[nx[x]+1],1,n);
158 if(x==n) break; x=nx[x]+1;
159
160 nx[l]=r;
161 flip[l]=o;
162
163 int q; read(q);
164 node tp=qry(1,1,n,q);
165 int ans;
166 if(flip[tp.l]) ans=find(rt[tp.l],1,n,tp.r-tp.l+1-(q-tp.l));
167 else ans=find(rt[tp.l],1,n,q-tp.l+1);
168 printf("%d\n",ans);
169 return 0;
170
线段树合并(代码片段)
线段树合并前置芝士动态开点线段树和权值线段树乍一看，线段树合并和上面那两个奇怪的东西有什么关系。其实，线段树合并的全称为动态开点权值线段树合并（雾如果对上面那两个奇怪的东西不理解可点开链接进行搜索（大... 查看详情
cf600elomsatgelral（线段树合并）(代码片段)
...号和（如果有多个出现数量最多的颜色，都算），(nle10^5)线段树合并用到线段树合并，线段树合并大概就是将两颗线段树的信息合并到一个上这里合并的大都是动态开点的线段树，因为如果要合并一颗满的线段 查看详情
线段树合并(代码片段)
Recently,TeaTreeacquirenewknoledgegcd(GreatestCommonDivisor),nowshewanttotestyou.Asweknow,TeaTreeisatreeandherrootisnode1,shehavennodesandn-1edge,foreachnodei,ithasit’svaluev[i].Foreverytwonodesiandj( 查看详情
线段树分裂合并(代码片段)
线段树分裂合并我先接触的是线段树合并所以先讲线段树合并。首先，用来合并的线段树必须是动态开点的。线段树合并所做的事就是合并两棵动态开点线段树的信息，对于两棵动态开点线段树，可能会存在一些公共节点，我们... 查看详情
线段树合并浅谈(代码片段)
...化版本的查询,我们就不得不求助于其他的算法,本篇将对线段树合并进行讲解线段树合并一般用于对子树的统计,一般的套路就是对树的每一个节点都开上一颗动态开点线段树,然后统计子树信息时,合并所有儿子信息,统计答案,然... 查看详情
线段树合并(代码片段)
...客的访问速度都明显变慢了ヽ(゜▽゜ )－C<(/;◇;)/~1.1线段树合并当你有两个数组时，并且希望快速合并两个数组时，最朴实的想法莫过于：枚举、合并，吧。for(inti=1;i<=n;++i)a[i]+=b[i];复杂度显然是(O(n))的。那么对于一个空间... 查看详情
luogup3359改造异或树线段树合并(代码片段)
删边转化为加边然后每次用线段树合并就行.....确确实实很简单然而为什么线段树合并跑不过$splay$的启发式合并，常数稍大了点...复杂度$O(nlogn)$#include<vector>#include<cstdio>#include<cstring>#include<iostream>#include<algorit... 查看详情
philosopher（set线段树合并）(代码片段)
...那么转换成区间求和，区间排序区间排序的方式可以采用线段树维护最大递增块来解决，外层用set来维护线段树的区间，然后利用线段树的合并分裂性质来操作即可#include<cstdio>#include<algorithm>#include<cstring>#include<qu 查看详情
例题线段树合并(代码片段)
...就可以，但是这个有很多种，所以给每个结点开一棵权值线段树就行，每个节点记录每种救济粮的数量，然后同样是利用差分的思想，只不过把差分数组改成了线段树的合并。#include<cstdio>#include 查看详情
神奇的操作——线段树合并（例题:bzoj2212）(代码片段)
什么是线段树合并？首先你需要动态开点的线段树。（对每个节点维护左儿子、右儿子、存储的数据，然后要修改某儿子所在的区间中的数据的时候再创建该节点。）考虑这样一个问题：你现在有两棵权值线段树（大概是用来维... 查看详情
codeforcesecr47fdominantindices（线段树合并）(代码片段)
一个比较显然的做法：对每棵子树用线段树维护其中的深度，线段树合并即可。 本来想用这个题学一下dsuontree，结果还是弃疗了。#include<iostream>#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#inc... 查看详情
线段树合并(代码片段)
3307:雨天的尾巴模板题。简单题调不过最好的方法是重构代码或者放一天然后重构代码。1//Achen2#include<algorithm>3#include<iostream>4#include<cstring>5#include<cstdlib>6#include<vector>7#include<cstdio>8#inc 查看详情
tunnelwarfare线段树区间合并|最大最小值(代码片段)
DuringtheWarofResistanceAgainstJapan,tunnelwarfarewascarriedoutextensivelyinthevastareasofnorthChinaPlain.Generallyspeaking,villagesconnectedbytunnelslayinaline.Exceptthetwoattheends,everyvillagewasdi 查看详情
hdu1540tunnelwarfare(区间合并)线段树(代码片段)
<题目链接>题目大意：题意：一个长度为n的线段，下面m个操作Dx表示将单元x毁掉R 表示修复最后毁坏的那个单元Qx 询问这个单元以及它周围有多少个连续的单元，如果它本身已经被毁坏了就是0。解题分析：用线段树... 查看详情
bzoj3545peaks线段树合并(代码片段)
离线乱搞。。。也就是一个线段树合并没什么#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;intn,m,q,tot,cnt,num,h[100001],a[100001],ans[500001],fa[100001],root 查看详情
poj3667hotel(线段树+区间合并)(代码片段)
HotelTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 20468 Accepted: 8924DescriptionThecowsarejourneyingnorthtoThunderBayinCanadatogainculturalenrichmentande 查看详情
codeforces600e.lomsatgelral(线段树合并）(代码片段)
Youaregivenarootedtreewithrootinvertex 1.Eachvertexiscolouredinsomecolour.Let‘scallcolour c dominatinginthesubtreeofvertex v iftherearenoothercoloursthatappearinthesubtreeofve 查看详情
p4556[vani有约会]雨天的尾巴（线段树合并）(代码片段)
传送门一道线段树合并首先不难看出树上差分我们把每一次修改拆成四个，在(u,v)分别放上一个，在(lca)和(fa[lca])各减去一个，那么只要统计一下子树里的总数即可然而问题就在于怎么统计。直接暴力肯定是要咕咕的，那么线段... 查看详情