最近考了小狗和李茂才的NOIP模拟题

让我第一次了解到原来树套树、动态点分治、费用流、LCT/树链剖分都在NOIP正常的考试范围内，这么看来我NOIP之后就要AFO了。

P.S.其实后来想想考这些也还算正常，NOIP考纲里面是有线段树、平衡树的，所以树套树就是前面两者的综合运用，点分治是分治思想的拓展运用，LCT是Splay的拓展，树链剖分就是线段树维护DFS序，所以考这些都没什么奇怪的说。【斜眼贼】

LMC1T2：对于一个排列，要删点，边删点边输出当前序列的逆序对数。

题解：将一个点的x坐标设为下标，y坐标设为权值，就变成了动态维护点集，还要查询一个点左上右下的点个数。于是可以用树套树做。我在考场上面写了线段树套平衡树，也算是过了。颓废着写了调了一个多小时，于是愉快地被duyegeD飞了。

考后我才知道有分块做法，然而感觉树套树也不难写，并且复杂度还是要优秀一些。总之没怎么多想了。膜一发考试的时候有这种思路但是没想出来的duyege

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
#define ll long long
int n,m,sb=0,a[N],qu[N],li[N];ll ans[N];bool d[N];
struct Point
 {
	 int s,v;Point *c[2],*fa;
 } b[N*40],*c[N*3];
inline int Read()
 {
	 int x=0;char y;
	 do y=getchar(); while (y<'0'||y>'9');
	 do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
	 return x;
 }
inline Point* NewNode(int x)
 {b[++sb].s=1;b[sb].v=x;return &b[sb];}
inline void Update(Point* x)
 {
	 x->s=1;
	 if (x->c[0]!=NULL) x->s+=x->c[0]->s;
	 if (x->c[1]!=NULL) x->s+=x->c[1]->s;
	 return;
 }
inline void Rotate(Point* x)
 {
	 Point *i=x->fa,*j=i->fa;bool k=i->c[0]==x;
	 if (j!=NULL) j->c[j->c[1]==i]=x;
	 if (x->c[k]!=NULL) x->c[k]->fa=i;
	 i->c[!k]=x->c[k];i->fa=x;
	 x->c[k]=i;x->fa=j;
	 Update(i);
	 return;
 }
void Splay(Point* x,int y)
 {
	 while (x->fa!=NULL)
	  {
		  if (x->fa->fa!=NULL)
		    Rotate((x->fa->fa->c[0]==x->fa)^(x->fa->c[0]==x)?x:x->fa);
	      Rotate(x);
	  }
	 Update(c[y]=x);
	 return;
 }
Point* Find(Point* x,int y,int z)
 {
	 if (x==NULL) return x;
	 Point *k;
	 if ((!z&&x->v>=y)||(z&&x->v>y)) k=Find(x->c[0],y,z);else k=Find(x->c[1],y,z);
	 if (!z)
	  {
		  if (k!=NULL) return k;
		  if (x->v<y) return x;else return NULL;
	  }
	 if (k!=NULL) return k;
	 if (x->v>y) return x;else return NULL;
 }
int Query(int x,int y,Point* z,int o)
 {
	 Point *k=Find(z,x,0),*l=Find(z,y,1);
	 Splay(k,o);k->c[1]->fa=NULL;Splay(l,o);
	 l->fa=c[o]=k;k->c[1]=l;Update(k);
	 k=l->c[0];return k!=NULL?k->s:0;
 }
int Query(int x,int y,int z,int o,int p,int e,int r)
 {
	 int i=x + y >> 1,j=z << 1,k=0;
	 if (x==o&&y==p) return Query(e,r,c[z],z);
	 if (o<=i) k+=Query(x,i,j,o,min(i,p),e,r);
	 if (p>i) k+=Query(i+1,y,j+1,max(o,i+1),p,e,r);
	 return k;
 }
void Insert(Point* x,int y)
 {
	 bool i=x->v<y;
	 if (x->c[i]==NULL) x->c[i]=NewNode(y),x->c[i]->fa=x;else Insert(x->c[i],y);
     x->s++;
	 return;
 }
void Insert(int x,int y,int z,int o,int p)
 {
	 int i=x + y >> 1,j=z << 1;
	 if (c[z]==NULL) c[z]=NewNode(p);else Insert(c[z],p),Splay(&b[sb],z);
	 if (x!=y)
	  if (i>=o) Insert(x,i,j,o,p);else Insert(i+1,y,j+1,o,p);
	 return;
 }
void Set_up(int x,int y,int z)
 {
	 int i=x + y >> 1,j=z << 1;
	 c[z]=NewNode(0);c[z]->c[1]=NewNode(n+1);c[z]->c[1]->fa=c[z];Update(c[z]);
	 if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
	 return;
 }
int main()
 {
	 n=Read();m=Read();
	 Set_up(1,n,1);
	 for (int i=1;i<=n;i++) li[a[i]=Read()]=i;
	 for (int i=1;i<=m;i++) d[qu[i]=Read()]=1;
	 for (int i=1;i<=n;i++)
	   if (!d[i]) ans[m+1]+=Query(1,n,1,1,li[i],i,n)+Query(1,n,1,li[i],n,1,i),Insert(1,n,1,li[i],i);
	 for (int i=m;i>=1;i--)
	   ans[i]+=Query(1,n,1,1,li[qu[i]],qu[i],n)+Query(1,n,1,li[qu[i]],n,1,qu[i]),
	   Insert(1,n,1,li[qu[i]],qu[i]),ans[i]+=ans[i+1];
	 for (int i=1;i<=m;i++)
	   printf("%lld\n",ans[i]);
     return 0;
 }

XG2T3：就是BZOJ1095，然而我想起来了的是QTREE4。由于论文上面的东西都不记得了，还是贼爷提醒才知道是点分治，一开始还一直在想分块做法= =真是羞耻。于是我还没写过点分治就开始写动态点分治了（虽然我现在还不知道到底算不算动态点分治），反正就是记录每次点分治的重心、每个点到重心的距离、每个点是重心的哪个子树，用n log n个set维护重心的每棵子树的点到重心距离、维护每个重心的每棵子树的最大距离以及每次点分治的答案。然后写了2个小时写出来了，调了一个小时，但是没发现一个不会对小数据造成多大影响的答案，于是过了样例交了之后还是挂了= =。后来发现把一个地方的j打成i了，改过来之后发现时间上面常数好大，2s时限在渣渣本机上根本跑不出来。然后这道题输入输出与1095稍有不同，还是贴上来代码好了= =（话说其实我们的考试可以考到4H，于是还算是有时间写这题）

当然，我考后才知道原来还有括号序列相关的线段树做法，膜一发考场上面有这种思路然后并没有想出来的duyege。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
multiset <int> a[N*2];
set <int> :: iterator it,ti;
int as=0,n,m,c[N*2][2],fi[N],sg[N][20],sn[N],ag[N],rt[N][20];
int s[N],ss=1,li[N],h[N][20],la[N],sgg[N][20],sz[N];
bool t[N];char yy;
inline int Read()
 {
	 int x=0;char y;
	 do y=getchar(); while (y<'0'||y>'9');
	 do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
	 return x;
 }
inline void Line(int x,int y)
 {
	 c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;
	 c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;
 }
int BFS(int x)
 {
	 int le=1,ri=1;
	 li[1]=x;la[x]=0;
	 for (;le<=ri;le++)
	  for (int i=fi[li[le]];i;i=c[i][1])
	    if (c[i][0]!=la[li[le]]&&!sn[c[i][0]])
	       li[++ri]=c[i][0],la[c[i][0]]=li[le];
     return ri;
 }
void Set_up(int x,int y)
 {
	 int ls=BFS(x),rf,ma=0,mx=0;
	 if (ls==1) {sn[x]=y-1;return;}
	 for (int i=ls;i>=1;i--)
	  {
		  sz[li[i]]=1;
		  for (int j=fi[li[i]];j;j=c[j][1])
		    if (c[j][0]!=la[li[i]]&&!sn[c[j][0]]) sz[li[i]]+=sz[c[j][0]];
	  }
	 for (int i=ls;i>=1;i--)
	  {
		  int k=0,l=0;
		  for (int j=fi[li[i]];j;j=c[j][1])
		    if (c[j][0]!=la[li[i]]&&!sn[c[j][0]]) k=max(k,sz[c[j][0]]),l+=sz[c[j][0]];
		  k=max(k,ls-1-l);
		  if (k<=ls/2) {rf=li[i];break;}
	  }
	 sn[rf]=y;BFS(rt[rf][y]=rf);ag[rf]=++as;a[as].insert(0);
	 for (int i=fi[rf];i;i=c[i][1])
	   if (!sn[c[i][0]]) sg[c[i][0]][y]=c[i][0],sgg[c[i][0]][y]=++as,
	   	 a[as].insert(h[c[i][0]][y]=1),rt[c[i][0]][y]=rf;
	 for (int i=2;i<=ls;i++)
	  for (int j=fi[li[i]];j;j=c[j][1])
	    if (!sg[c[j][0]][y]&&!sn[c[j][0]])
	      a[sgg[sg[c[j][0]][y]=sg[li[i]][y]][y]].insert(h[c[j][0]][y]=h[li[i]][y]+1),
	      rt[c[j][0]][y]=rf;
	 for (int i=fi[rf];i;i=c[i][1])
	  if (!sn[c[i][0]])
	   {
	       it=a[sgg[c[i][0]][y]].end();a[ag[rf]].insert(*(--it));
		   if (*it>ma) mx=ma,ma=*it;else if (*it>mx) mx=*it;
	   }
	 if (mx) a[0].insert(mx+ma);else a[0].insert(ma);
	 for (int i=fi[rf];i;i=c[i][1])
	  if (!sn[c[i][0]]) Set_up(c[i][0],y+1);
 	 return;
 }
void Insert(int x)
 {
	 for (int i=1;i<=sn[x];i++)
	  if (rt[x][i]==x)
	   {
		   a[ag[x]].insert(0);
		   if (a[ag[x]].size()==2) it=a[ag[x]].begin(),a[0].insert(*(++it));
	   }else
	   {
		   int k=0,l=0;ti=a[sgg[sg[x][i]][i]].end();bool e=0;
		   if (ti==a[sgg[sg[x][i]][i]].begin()) e=1;else ti--;a[sgg[sg[x][i]][i]].insert(h[x][i]);
		   if (!e&&h[x][i]<=*ti) continue;
		   if (a[ag[rt[x][i]]].size()>1)
			  it=a[ag[rt[x][i]]].end(),l=*(--it)+*(--it),it=a[0].lower_bound(*it),a[0].erase(it);
		   if (!e) it=a[ag[rt[x][i]]].lower_bound(*ti),a[ag[rt[x][i]]].erase(it);
		   a[ag[rt[x][i]]].insert(h[x][i]);
		   if (a[ag[rt[x][i]]].size()>1) it=a[ag[rt[x][i]]].end(),k=*(--it)+*(--it),a[0].insert(k);
	   }
	 return;
 }
void Delete(int x)
 {
	 for (int i=1;i<=sn[x];i++)
	  if (rt[x][i]==x)
	   {
		   a[ag[x]].erase(0);
		   if (a[ag[x]].size()==1) it=a[ag[x]].begin(),it=a[0].lower_bound(*it),a[0].erase(it);
	   }else
	   {
	   	   int k=0,l=0,q=0,w=0,e=0;it=a[sgg[sg[x][i]][i]].end();k=*(--it);
		   it=a[sgg[sg[x][i]][i]].lower_bound(h[x][i]);
		   a[sgg[sg[x][i]][i]].erase(it);
		   if (h[x][i]<k) continue;
		   if (a[ag[rt[x][i]]].size()>1)
		     it=a[ag[rt[x][i]]].end(),q=*(--it)+*(--it),
		     it=a[0].lower_bound(q),a[0].erase(it);
		   it=a[ag[rt[x][i]]].lower_bound(k);a[ag[rt[x][i]]].erase(it);
		   if (a[sgg[sg[x][i]][i]].size())
		     it=a[sgg[sg[x][i]][i]].end(),a[ag[rt[x][i]]].insert(*(--it));
		   if (a[ag[rt[x][i]]].size()>1)
		     it=a[ag[rt[x][i]]].end(),q=*(--it)+*(--it),a[0].insert(q);
	   }
	 return;
 }
int main()
 {
	 t[n=Read()]=1;m=Read();
	 for (int i=1;i<n;i++) Line(Read(),Read()),t[i]=1;
	 Set_up(1,1);
	 for (int i=1;i<=m;i++)
	  {
		 int k=Read();if (t[k]) Delete(k);else Insert(k);
		 t[k]=!t[k];it=a[0].end();printf("%d\n",*(--it));
	  }
	 return 0;
 }

感觉最近真是被正解的duyegeD肥了