给了签到题，但除了签到题其他的什么也不会。。。。
T1 数数
人均$AC$，没什么好说的，就是排个序，然后双指针交换着往中间移
1 #include<bits/stdc++.h>
2 #define int long long
3 using namespace std;
4 const int NN=3e5+5;
5 int n,a[NN],ans[NN],id[NN],cha[NN];
6 inline bool cmp(int a,int b){return a>b;}
7 inline void spj(){
8 for(int i=1;i<(1<<n);i++){
9 int sta=i,cnt=0,tmp=0;
10 for(int j=n;j;j--){
11 if(sta&1) id[++cnt]=j;
12 sta>>=1;
13 }
14 for(int j=1;j<=cnt;j++)
15 for(int k=j;k<=cnt;k++)
16 tmp+=abs(a[id[j]]-a[id[k]]);
17 ans[cnt]=max(ans[cnt],tmp);
18 }for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
19 }
20 namespace WSN{
21 inline short main(){
22 scanf("%lld",&n);
23 for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
24 if(n<=5) {spj();return 0;}
25 sort(a+1,a+n+1,cmp);
26 ans[1]=0; ans[2]=a[1]-a[n]; cha[2]=ans[2]; cha[1]=0;
27 int l=1,r=n;
28 while(l<r){
29 int num=l+n-r+1;
30 if(l==n-r+1) ans[num+1]+=ans[num]+cha[num],++l,cha[num+1]=cha[num];
31 else{
32 ans[num+1]+=cha[num]+a[l]-a[--r]+ans[num];
33 cha[num+1]+=a[l]-a[r]+cha[num];
34 }
35 }for(int i=1;i<=n;i++) printf("%lld\n",ans[i]);
36 return 0;
37 }
38 }
39 signed main(){return WSN::main();}
View Code
T2 数树
题解上说是插头$dp$，就直接跳过先改$T3$了
T3 鼠树
能和二逼平衡树相媲美的码量，思路却不知道比那个难多少
整体的思路就是只记录黑点的信息，然后询问的时候就找到管辖白点的黑点
然后进行更改和查询操作
那么关于找管辖白点的黑点，可以使用树状数组+树链剖分+二分答案轻松解决
1 inline int find_belong(int x){
2 if(col[x]) return x;
3 while(top[x]!=1){
4 if(zhao(dfn[x])-zhao(dfn[top[x]]-1)==0){x=fa[top[x]];continue;}
5 if(col[x]) return x;
6 int l=dfn[top[x]],r=dfn[x],ans;
7 while(l<=r){
8 int mid=l+r>>1;
9 if(zhao(dfn[x])-zhao(mid-1)) ans=mid,l=mid+1;
10 else r=mid-1;
11 }
12 return rk[ans];
13 }
14 int l=1,r=dfn[x],ans;
15 while(l<=r){
16 int mid=l+r>>1;
17 if(zhao(dfn[x])-zhao(mid-1)) ans=mid,l=mid+1;
18 else r=mid-1;
19 }
20 return rk[ans];
21 }
然后考虑如何实现各种操作。
操作1，先找管辖点，直接查他的权值
操作2，直接改那个点的值
操作3，分情况，如果这个点是白点，找到他以下黑点的信息总和，然后找到跟他一伙的白点的数量，然后找到他们的权值，算出来加上就行
如果是黑点，只找他子树里黑点的总和
操作4，直接改子树信息
操作5，改成黑点，他的归属点管辖的点个数减少，分步修改即可
操作6，维护一个差分，修改的时候带上，查询的时候加上，因为你要存下来这些退化的点的信息。
1 #include<bits/stdc++.h>
2 #define lid (id<<1)
3 #define rid (id<<1|1)
4 #define int unsigned int
5 using namespace std;
6 namespace AE86{
7 inline int read(){
8 int x=0,f=1; char ch=getchar();
9 while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
10 while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
11 return x*f;
12 }
13 inline void write(int x,char sp){
14 char ch[20]; int len=0;
15 if(x<0){ putchar('-'); x=~x+1; }
16 do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);
17 for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);
18 }
19 } using namespace AE86;
20
21 const int NN=3e5+5;
22 int n,m,opt,K,W,col[NN];
23 struct SNOW{int to,next;};SNOW e[NN<<1]; int head[NN],rp;
24 inline void add(int x,int y){
25 e[++rp]=(SNOW){y,head[x]};head[x]=rp;
26 e[++rp]=(SNOW){x,head[y]};head[y]=rp;
27 }
28 namespace Tree_division{
29 int fa[NN],son[NN],rk[NN],dfn[NN],top[NN],dep[NN],siz[NN],cnt;
30 inline void dfs1(int f,int x){
31 siz[x]=1; dep[x]=dep[f]+1; fa[x]=f;
32 for(int i=head[x];i;i=e[i].next){
33 int y=e[i].to; if(y==f) continue;
34 dfs1(x,y); siz[x]+=siz[y];
35 if(siz[son[x]]<siz[y]) son[x]=y;
36 }
37 }
38 inline void dfs2(int x,int t){
39 dfn[x]=++cnt; rk[cnt]=x; top[x]=t;
40 if(!son[x]) return; dfs2(son[x],t);
41 for(int i=head[x];i;i=e[i].next){
42 int y=e[i].to;
43 if(y!=fa[x]&&y!=son[x]) dfs2(y,y);
44 }
45 }
46 }using namespace Tree_division;
47
48 namespace Tree_array{
49 int tr[NN];
50 inline int lowbit(int x){return x&(-x);}
51 inline void charu(int x,int v){for(;x<=n;x+=lowbit(x)) tr[x]+=v;}
52 inline int zhao(int x){int ans=0;for(;x;x-=lowbit(x)) ans+=tr[x];return ans;}
53 }using namespace Tree_array;
54
55 namespace SNOWtree{
56 int ll[NN<<2],rr[NN<<2];
57 int num[NN<<2],sum[NN<<2],laz[NN<<2],mul[NN<<2];
58 int cha[NN<<2],lac[NN<<2];
59 inline void pushdown(int id){
60 if(laz[id]){
61 mul[lid]+=num[lid]*laz[id]; mul[rid]+=num[rid]*laz[id];
62 sum[lid]+=laz[id]; sum[rid]+=laz[id];
63 laz[lid]+=laz[id]; laz[rid]+=laz[id];
64 }
65 if(lac[id]){
66 int mid=ll[id]+rr[id]>>1;
67 cha[lid]+=lac[id]*(mid-ll[id]+1); cha[rid]+=lac[id]*(rr[id]-mid);
68 lac[lid]+=lac[id]; lac[rid]+=lac[id];
69 }
70 laz[id]=lac[id]=0;
71 }
72 inline void pushup(int id){
73 if(ll[id]==rr[id]) return;
74 num[id]=num[lid]+num[rid]; sum[id]=sum[lid]+sum[rid];
75 mul[id]=mul[lid]+mul[rid]; cha[id]=cha[lid]+cha[rid];
76 }
77 inline void build(int id,int l,int r){
78 ll[id]=l; rr[id]=r;
79 if(l==r) return; int mid=l+r>>1;
80 build(lid,l,mid); build(rid,mid+1,r);
81 }
82 inline void insert(int id,int pos,int shu,int val){//插入黑点
83 if(ll[id]==rr[id]){
84 num[id]=shu; sum[id]=val;
85 mul[id]=shu*val;
86 return;
87 }pushdown(id);int mid=ll[id]+rr[id]>>1;
88 if(pos<=mid) insert(lid,pos,shu,val);
89 else insert(rid,pos,shu,val);
90 pushup(id);
91 }
92 inline void clear(int id,int pos){//删除黑点
93 if(ll[id]==rr[id]){
94 num[id]=sum[id]=mul[id]=0;
95 return;
96 }pushdown(id);int mid=ll[id]+rr[id]>>1;
97 if(pos<=mid) clear(lid,pos);
98 else clear(rid,pos);
99 pushup(id);
100 }
101 inline void change(int id,int l,int r,int val){//加w
102 if(l<=ll[id]&&rr[id]<=r){
103 sum[id]+=val; laz[id]+=val;
104 mul[id]+=val*num[id];
105 return;
106 }pushdown(id);int mid=ll[id]+rr[id]>>1;
107 if(l<=mid) change(lid,l,r,val);
108 if(r>mid) change(rid,l,r,val);
109 pushup(id);
110 }
111 inline void update(int id,int l,int r,int val){//加差分
112 if(l<=ll[id]&&rr[id]<=r){
113 cha[id]+=val*(rr[id]-ll[id]+1);
114 lac[id]+=val;
115 return;
116 }pushdown(id); int mid=ll[id]+rr[id]>>1;
117 if(l<=mid) update(lid,l,r,val);
118 if(r>mid) update(rid,l,r,val);
119 pushup(id);
120 }
121 inline int look(int id,int l,int r){//区间求差分
122 if(l<=ll[id]&&rr[id]<=r) return cha[id];
123 pushdown(id); int mid=ll[id]+rr[id]>>1,ans=0;
124 if(l<=mid) ans+=look(lid,l,r);
125 if(r>mid) ans+=look(rid,l,r);
126 return ans;
127 }
128 inline int query(int id,int l,int r){//区间求w×c
129 if(l<=ll[id]&&rr[id]<=r) return mul[id];
130 pushdown(id);int mid=ll[id]+rr[id]>>1,ans=0;
131 if(l<=mid) ans+=query(lid,l,r);
132 if(r>mid) ans+=query(rid,l,r);
133 return ans;
134 }
135 inline int search(int id,int l,int r){//区间求c
136 if(l<=ll[id]&&rr[id]<=r) return num[id];
137 pushdown(id);int mid=ll[id]+rr[id]>>1,ans=0;
138 if(l<=mid) ans+=search(lid,l,r);
139 if(r>mid) ans+=search(rid,l,r);
140 return ans;
141 }
142 inline int found(int id,int pos){//单点求w
143 if(ll[id]==rr[id]) return sum[id];
144 pushdown(id);int mid=ll[id]+rr[id]>>1;
145 if(pos<=mid) return found(lid,pos);
146 else return found(rid,pos);
147 }
148 }using namespace SNOWtree;
149
150 inline int find_belong(int x){
151 if(col[x]) return x;
152 while(top[x]!=1){
153 if(zhao(dfn[x])-zhao(dfn[top[x]]-1)==0){x=fa[top[x]];continue;}
154 if(col[x]) return x;
155 int l=dfn[top[x]],r=dfn[x],ans;
156 while(l<=r){
157 int mid=l+r>>1;
158 if(zhao(dfn[x])-zhao(mid-1)) ans=mid,l=mid+1;
159 else r=mid-1;
160 }
161 return rk[ans];
162 }
163 int l=1,r=dfn[x],ans;
164 while(l<=r){
165 int mid=l+r>>1;
166 if(zhao(dfn[x])-zhao(mid-1)) ans=mid,l=mid+1;
167 else r=mid-1;
168 }
169 return rk[ans];
170 }
171
172 namespace WSN{
173 inline short main(){
174 // freopen("pastel5.in","r",stdin);
175 // freopen("1.in","r",stdin);
176 // freopen("1.out","w",stdout);
177 n=read();m=read();
178 for(int i=2;i<=n;i++) add(read(),i);
179 dfs1(0,1); dfs2(1,1); build(1,1,n);
180 col[1]=1; charu(1,1); insert(1,1,siz[1],0);
181 while(m--){
182 opt=read();K=read(); if(opt==2||opt==4) W=read();
183 if(opt==1){
184 int ruler=find_belong(K);
185 write(found(1,dfn[ruler])+look(1,dfn[K],dfn[K]),'\n');
186 }
187 if(opt==2) change(1,dfn[K],dfn[K],W);
188 if(opt==3){
189 int ruler=find_belong(K),res=0;
190 int cheng=query(1,dfn[K],dfn[K]+siz[K]-1);
191 int geshu=siz[K]-search(1,dfn[K],dfn[K]+siz[K]-1);
192 int Sum=found(1,dfn[ruler]);
193 if(!col[K]) res+=geshu*Sum;
194 res+=cheng; write(res+look(1,dfn[K],dfn[K]+siz[K]-1),'\n');
195 }
196 if(opt==4) change(1,dfn[K],dfn[K]+siz[K]-1,W);
197 if(opt==5){
198 int ruler=find_belong(K);
199 int NUM=siz[K]-search(1,dfn[K],dfn[K]+siz[K]-1);
200 int VAL=found(1,dfn[ruler]);
201 col[K]=1; charu(dfn[K],1); insert(1,dfn[K],NUM,VAL);
202 insert(1,dfn[ruler],search(1,dfn[ruler],dfn[ruler])-NUM,VAL);
203 }
204 if(opt==6){
205 int Siz=search(1,dfn[K],dfn[K]);
206 col[K]=0; charu(dfn[K],-1);
207 int ruler=find_belong(K);
208 int Cha=found(1,dfn[K])-found(1,dfn[ruler]);
209 insert(1,dfn[ruler],search(1,dfn[ruler],dfn[ruler])+Siz,found(1,dfn[ruler]));
210 update(1,dfn[K],dfn[K]+siz[K]-1,Cha);
211 clear(1,dfn[K]);
212 change(1,dfn[K],dfn[K]+siz[K]-1,-Cha);
213 }
214 }
215 return 0;
216 }
217 }
218 signed main(){return WSN::main();}
200行，我写过的最长代码
T4 ckw的树
沽了