POI18填坑计划

这个感觉一路都推的比较顺。。只不过经常SB进了细节坑

现在完成了:

16

[Plot]:二分答案显然。。维护凸包的时候顺便查询插入点的对踵点和旁边两个点更新答案就好。。由于只有插入点的动态凸包随便搞就好。。

[Tree Rotations]:SB题。。可以看出每个点的状态对答案的贡献是独立的。。然后就treap启发式合并就好。然后那个什么n log n的treap直接合并可以做这个的加强版吧。。但是treap启发式合并在加强版还是能拿97分所以就没写n log n了。

[Conspiracy]:很容易可以分析出只会有O(n)种答案。而且答案之间最多只会替换一个点。。一堆显然的性质套上去特判就好了。。初始答案只要按度数从大到小取。还要注意特判有一边为空集的情况。

[Lighting Conductor]:一开始以为n*sqrt(n)的RMQ过的去。。后来发现有决策单调性。。然后就直接单调队列维护就好了。。

[Lollipop]:前缀后缀扫一遍。然后发现当1~i的和大于查询数并且第i+1个数为1的时候就可以直接取了。所以排序+扫几遍。

[Temperature]:一个区间是可行的当且仅当不存在i<j使得Li>Rj。归纳法可证。于是就只要单调队列扫一遍就好。。一开始没看空间范围直接上了个线段树MLE。。虽然改一改线段树也是能过的。。

[Strongbox]:先将最后一个数和n gcd一下。然后将得到的这个数和前面的数都gcd一下。然后求n的每个因子可不可以作为答案。并且每个因子可以最多转移到log个节点。

[Garbage]:一眼觉得可以求欧拉回路然后直接算出答案。。但是觉得麻烦就写了一个乱搞结果还是T了。。

[Dynamite]:一开始觉得二分答案+每次找到最深未炸节点炸掉。后面那东西用链表维护是O(n)的。但是还是SB了一下把这样n/Ans次炸这棵树的复杂度算成了O(n)。。= =靠谱做法是DP。。复杂度就是n log n

[Meteors]:整体二分就好。。

[Party]:经典题。讲课讲过很多次。每次选择一个未删除的虚边上两点删掉就好。由于存在团所以肯定有至少一个点不在团上。所以最多删n/3次。。

[Difference]:考虑右端点为k的答案贡献肯定是把最多的算作Ck。然后一路维护前缀和还有Si-Sj的极值即可

[Sticks]:一开始naive不知道为什么觉得要用set。。排个序然后随便维护一下找出最大的异色的前两个棍子。。不知道那个颜色个数小于等于50是怎么用的。。复杂度明显无关的。。

[Inspection]:满足最大子树不超过一半的也就只有重心了吧。。然后直接特判一下最后一步是走最深节点还是只能走其它子树就好了。。

[Programming Contest]:很容易脑补出一个性质:每次Hungary就是最优解。。不会证但是感觉显然。。然后我想了两种写法一种动态删边,一种动态加边。然后作死写了第一种果然有后效性。。两个都是n^3的。。

[Shift]:很容易看出没有解的情况只有n为奇数并且给定状态的逆序对数跟目标状态不同。其余情况我们都可以构造出解。然后我只会n^2次的做法了。。比如每次把一个数往前面提。。比如每次将任意一个三元组变成最优状态(因为每次都会减少一个逆序对所以肯定是n^2的)。。当然感觉上还是前面那个常数会小一些。。我的写法丑了真尼玛调好久。。

[Periodicity]:我记得这题被出到过某ZHZX的NOIP模拟题里面。。简直sxbk。。

数据结构乱做

最近在补课件上一些题目。就只放CLS的一些题目上来好了。。

感觉这些题做起来真是要死。毕竟代码能力弱都要调好久= =做到后面感觉到了深深的绝望。

本来还想开坑Sone1,而且本来想写课件上面给出的LCT套ETT的做法,但是n log^2 n,10w范围,40s时限,常数还这么大。感觉很不资瓷的样子所以写了一半细思之下就退坑了。

BZOJ4068 [CTSC2015] App:首先显然这是个拟阵。然后据说就可以得出一个性质:新加入的任务最多只会替换原来的一个任务。。删除同理,就是这个结论的逆,也就是删除一个任务最多只会加入一个任务到答案中。不管这些东西怎么来之后就是很裸的线段树了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
#define N 300050
#define INF 0x3f7f7f7f
#define fr first
#define sc second
#define ll long long
ll ans;char ch[4];bool b[N];int st,n,m,v[N][2],ne[N];
map <pair <int,int>,int> Ha;
multiset <pair <int,int> > s[N][2];
set <pair <int,int> > :: iterator it;
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
struct Segment_Tree
 {
 	int mi[N*4],ad[N*4];pair <int,int> ma[N*4];
 	void Set_up(int x,int y,int z)
 	 {
 	 	int i=x + y >> 1,j=z << 1;
 	 	mi[z]=x;ma[z]=make_pair(-INF,0);
 	 	if (x!=y) Set_up(x,i,j),Set_up(i+1,y,j+1);
 	 }
 	inline void adj(int x,int y,int z)
 	 {
 	 	int j=z << 1;
 	 	if (!ad[z]) return;
 	 	if (x!=y) ad[j]+=ad[z],ad[j+1]+=ad[z];
 	 	mi[z]+=ad[z];ad[z]=0;
 	 }
 	inline pair <int,int> Getmax(pair <int,int> x,pair <int,int> y,bool flag)
 	 {return flag?(x.fr<y.fr?y:x):(y.fr<x.fr?x:y);}
 	inline void Update(int x,int y,int z,bool flag)
 	 {
 	 	int j=z << 1;
 	 	if (x==y)
 	 	 {
 	 	 	it=s[x][flag].end();
 	 	 	if (it!=s[x][flag].begin())
 	 	 	  ma[z]=*(--it); else
 	 	 	  ma[z]=make_pair(-INF,0);
 	 	 	return;
 	 	 }
 	 	mi[z]=min(mi[j],mi[j+1]);ma[z]=Getmax(ma[j],ma[j+1],flag);
 	 }
 	inline pair <int,int> Trans(int y,bool flag)
 	 {return make_pair(flag?-v[y][1]:v[y][1],y);}
 	void Delete(int x,int y,int z,int o,int p,bool flag)
 	 {
 	 	int i=x + y >> 1,j=z << 1;adj(x,y,z);
 	 	if (x==y)
 	 	 {
 	 	 	if (flag) ad[z]=1;
 	 	 	s[x][flag].erase(Trans(p,flag));
 	 	 	adj(x,y,z);Update(x,y,z,flag);return;
 	 	 }
 	 	if (o>i) Delete(i+1,y,j+1,o,p,flag),adj(x,i,j); else
 	 	  Delete(x,i,j,o,p,flag),
 	 	  ad[j+1]+=flag?1:0,adj(i+1,y,j+1);
 	 	Update(x,y,z,flag);
 	 	return;
 	 }
 	void Insert(int x,int y,int z,int o,int p,bool flag)
 	 {
 	 	int i=x + y >> 1,j=z << 1;adj(x,y,z);
 	 	if (x==y)
 	 	 {
 	 	 	if (flag) ad[z]=-1;
 	 	 	s[x][flag].insert(Trans(p,flag));
 	 	 	adj(x,y,z);Update(x,y,z,flag);return;
 	 	 }
 	 	if (o>i) Insert(i+1,y,j+1,o,p,flag),adj(x,i,j); else
 	 	  Insert(x,i,j,o,p,flag),
 	 	  ad[j+1]+=flag?-1:0,adj(i+1,y,j+1);
 	 	Update(x,y,z,flag);
 	 	return;
 	 }
 	pair <int,int> Query(int x,int y,int z,int o,int p,bool flag)
 	 {
 	 	int i=x + y >> 1,j=z << 1;adj(x,y,z);
 	 	if (x==o&&y==p) return ma[z];
 	 	if (p<=i) return Query(x,i,j,o,p,flag); else
 	 	 if (o>i) return Query(i+1,y,j+1,o,p,flag); else
 	 	   return Getmax(Query(x,i,j,o,i,flag),Query(i+1,y,j+1,i+1,p,flag),flag);
 	 }
 	int Find_Left(int x,int y,int z,int o)
 	 {
 	 	int i=x + y >> 1,j=z << 1,k=0;adj(x,y,z);
 	 	if (x==y) return !mi[z]?x:0; else
 	 	  adj(x,i,j),adj(i+1,y,j+1);
 	 	if (!mi[j]&&o<=i) k=Find_Left(x,i,j,o);
 	 	if (!k&&!mi[j+1]) k=Find_Left(i+1,y,j+1,max(o,i+1));
 	 	return k;
 	 }
 	int Find_Right(int x,int y,int z)
 	 {
 	 	int i=x + y >> 1,j=z << 1;adj(x,y,z);
 	 	if (x==y) return !mi[z]?x:0; else
 	 	  adj(x,i,j),adj(i+1,y,j+1);
 	 	if (!mi[j+1]) return Find_Right(i+1,y,j+1); else
 	 	  return Find_Right(x,i,j);
 	 }
 } A,B;
void Delete(int x,int y)
 {
 	int sg=Ha[make_pair(x,y)];
 	Ha[make_pair(x,y)]=ne[sg];
 	if (!b[sg]) {B.Delete(1,n,1,x,sg,false);return;}
 	A.Delete(1,n,1,x,sg,true);int k=A.Find_Right(1,n,1);
 	k=B.Query(1,n,1,k+1,n,false).sc;ans-=y;b[sg]=false;
 	if (k)
 	  B.Delete(1,n,1,v[k][0],k,false),
 	  A.Insert(1,n,1,v[k][0],k,true),
 	  ans+=v[k][1],b[k]=true;
 	return;
 }
void Insert(int x,int y)
 {
 	v[++st][0]=x;v[st][1]=y;
 	ne[st]=Ha[make_pair(x,y)];Ha[make_pair(x,y)]=st;
 	int k=A.Find_Left(1,n,1,x);
 	if (!k&&y>=0)
 	  {A.Insert(1,n,1,x,st,true);b[st]=true;ans+=y;return;}
 	k=A.Query(1,n,1,1,k,true).sc;
 	if (v[k][1]>=y) B.Insert(1,n,1,x,st,false); else
 	 {
 	 	A.Delete(1,n,1,v[k][0],k,true);b[k]=false;
 	 	B.Insert(1,n,1,v[k][0],k,false);
 	 	A.Insert(1,n,1,x,st,true);b[st]=true;
 	 	ans+=y-v[k][1];
 	 }
 	return;
 }
int main()
 {
 	n=Read();m=Read();A.Set_up(1,n,1);B.Set_up(1,n,1);
 	for (int i=1;i<=m;i++)
 	 {
 	 	int k,l;scanf("%s%d%d",ch,&k,&l);
 	 	if (ch[0]=='D') Delete(k,l); else Insert(k,l);
 	 	printf("%lld\n",ans);
 	 }
 	return 0;
 }

BZOJ3435 [WC2014]紫荆花之恋:经典题,替罪羊树套点分治套treap。因为替罪羊维持平衡的部分出了些微妙的错误导致TLE一直都没看出来= =

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;
#define N 100050
#define M 6000050
#define P 4000050
#define INF (int)1e9
#define eps 0.78
#define ll long long
int c[N*2][3],h[N],dep[N],r[N],li[N],n,m,ss=1;
ll ans;int dis[N][30],fi[N],Dis[N];bool Flag;
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,int z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];fi[x]=ss;c[ss][2]=z;
 	c[++ss][0]=x;c[ss][1]=fi[y];fi[y]=ss;c[ss][2]=z;
 }
struct Node
 {
 	Node *c[2];int v,s,val;
 } used[P],*unused[P],*pool = used,**top = unused,*rt[N][2],Emp,*emp=&Emp;
struct Balance_Tree
 {
 	inline Node* Get(int x)
 	 {
 	 	Node *k = (top != unused) ? *--top : pool++;
 	 	k->c[0]=k->c[1]=emp;
 	 	k->s=1;k->v=x;k->val=rand();
 	 	return k;
 	 }
 	inline void Update(Node *x)
 	 {x->s=x->c[0]->s+x->c[1]->s+1;}
 	void Rotate(Node* &x,Node* y)
 	 {
 	 	bool k=y==x->c[0];
 	 	x->c[!k]=y->c[k];y->c[k]=x;
 	 	y->s=x->s;Update(x);x=y;
 	 	return;
 	 }
 	void Insert(Node* &x,Node* y)
 	 {
 	 	bool flag=y->v>x->v;
 	 	if (x==emp) {x=y;return;} else x->s++;
 	 	Insert(x->c[flag],y);
 	 	if (x->c[flag]->val>x->val)
 	 	  Rotate(x,x->c[flag]);
 	 	return;
 	 }
 	int Query(Node* x,int y)
 	 {
 	 	if (x==emp) return 0;
 	 	if (y>=x->v) return x->c[0]->s+1+Query(x->c[1],y); else
 	 	  return Query(x->c[0],y);
 	 }
 	void Clear(Node* &x)
 	 {
 	 	if (x==emp) return;
 	 	*top++ = x;
 	 	Clear(x->c[0]);Clear(x->c[1]);
 	 	x=emp;
 	 }
 	Node* Rebuild(int x,int y)
 	 {
 	 	Node* Rt=Get(dis[li[1]][y]-r[li[1]]);
 	 	for (int i=2;i<=x;i++)
 	 	  Insert(Rt,Get(dis[li[i]][y]-r[li[i]]));
 	 	return Rt;
 	 }
 } B;
struct Divide_Tree
 {
 	int suf[N],cnt[N],sg[N],sz[N],Rt,Sg;
 	int Get_Size(int x)
 	 {
 	 	int le=1,ri=1;li[1]=x;sz[x]=-1;
 	 	for (;le<=ri;le++)
 	 	 for (int i=fi[li[le]];i;i=c[i][1])
 	 	  if (!sz[c[i][0]]&&!sg[c[i][0]])
 	 	    sz[li[++ri]=c[i][0]]=-1;
 	 	return ri;
 	 }
 	int Get_Rt(int Cnt)
 	 {
 	 	int Ctr=li[1];
 	 	for (int i=Cnt;i>=1;i--)
 	 	 {
 	 	 	sz[li[i]]=1;
 	 	 	for (int j=fi[li[i]];j;j=c[j][1])
 	 	 	 if (!sg[c[j][0]]&&sz[c[j][0]]>0) sz[li[i]]+=sz[c[j][0]];
 	 	 }
 	 	while (true)
 	 	 {
 	 	 	bool flag=false;
 	 	 	for (int i=fi[Ctr];i;i=c[i][1])
 	 	 	 if (sz[c[i][0]]<sz[Ctr]&&!sg[c[i][0]]&&sz[c[i][0]]*2>=Cnt)
 	 	 	  {Ctr=c[i][0];flag=true;break;}
 	 	 	if (!flag) break;
 	 	 }
 	 	for (int i=1;i<=Cnt;i++) sz[li[i]]=0;
 	 	return Ctr;
 	 }
 	void DFS(int x,int y,int z)
 	 {
 	 	for (int i=fi[x];i;i=c[i][1])
 	 	 if (!sg[c[i][0]]&&c[i][0]!=y)
 	 	   dis[c[i][0]][z]=dis[x][z]+c[i][2],
 	 	   DFS(c[i][0],x,z);
 	 	return;
 	 }
 	void Rebuild(int x,int y,int z)
 	 {
 	 	int Cnt=Get_Size(x),Ctr=Get_Rt(Cnt);
 	 	dis[Ctr][y]=0;DFS(Ctr,0,y);sg[Ctr]=y;
 	 	if (z) suf[Ctr]=z; else
		   suf[Rt=Ctr]=0,rt[Ctr][1]=emp;
 	 	rt[Ctr][0]=B.Rebuild(Cnt,y);cnt[Ctr]=Cnt;
 	 	if (y>1) rt[Ctr][1]=B.Rebuild(Cnt,y-1);
 	 	for (int i=fi[Ctr];i;i=c[i][1])
 	 	 if (!sg[c[i][0]]) Rebuild(c[i][0],y+1,Ctr);
 	 	return;
 	 }
 	void Clear(int x)
 	 {
 	 	if (!sg[x]||sg[x]<Sg) return;sg[x]=0;
 	 	B.Clear(rt[x][0]);B.Clear(rt[x][1]);
 	 	for (int i=fi[x];i;i=c[i][1]) Clear(c[i][0]);
 	 }
 	void Get(int x,int y)
 	 {
 	 	cnt[x]=1;sg[x]=sg[suf[x]]+1;int ma=0;
 	 	rt[x][0]=B.Get(-y);rt[x][1]=B.Get(c[ss][2]-y);
 	 	memcpy(dis[x],dis[suf[x]],sizeof dis[suf[x]]);
 	 	for (int i=1;i<sg[x];i++) dis[x][i]+=c[ss][2];
 	 	dis[x][sg[x]]=0;
 	 	for (int i=suf[x],j=sg[x]-1;i;i=suf[i],j--)
 	 	 {
 	 	 	cnt[i]++;
 	 	 	if (j-1&&cnt[i]/(cnt[suf[i]]+1.0)>eps) ma=suf[i];
 	 	 	ans+=B.Query(rt[i][0],y-dis[x][j]);
 	 	 	B.Insert(rt[i][0],B.Get(dis[x][j]-y));
 	 	 	if (j-1)
 	 	 	  ans-=B.Query(rt[i][1],y-dis[x][j-1]),
 	 	 	  B.Insert(rt[i][1],B.Get(dis[x][j-1]-y));
 	 	 }
 	 	if (ma)
 	 	  Sg=sg[ma],Clear(ma),Rebuild(ma,Sg,suf[ma]);
 	 	return;
 	 }
 } A;
int main()
 {
 	Read();n=Read();Read();Read();
 	A.Rt=1;Emp.c[0]=Emp.c[1]=&Emp;
 	srand(23335900);//Orz TATQAQ2333 and yyh5900
 	A.Get(1,r[1]=Read());puts("0");
 	for (int i=2;i<=n;i++)
 	 {
 	 	int q=Read()^(ans%INF),w=Read();r[i]=Read();
 	 	h[i]=h[q]+1;dep[i]=dep[q]+w;
 	 	Line(i,q,w);A.suf[i]=q;
 	 	A.Get(i,r[i]);printf("%lld\n",ans);
 	 }
 	return 0;
 }

BZOJ3068 小白树:直接枚举断边就好。然后答案就是分成的两棵树的重心。至于为什么因为每种方案都对应了至少一个断边,然而每种断边的最优解又肯定是在两棵树重心处。所以虽然不一定一个两棵树的重心的断边一定是枚举的那个但是这种方案肯定是比其它断边为这条的方案更优的。所以就只要求出一个东西:一棵子树的重心和对应答案是什么。去掉这棵子树的重心和对应答案是什么。前面那个东西很好求,只需要求出一个点每棵子树的答案然后再找出自身的重心在哪棵子树,然后暴力往上移动就好。这种方法类似于启发式合并,复杂度也是一样。至于求一棵子树的补的重心,我们考虑二分答案。首先设去掉的子树的父亲是i,那么如果在i的某棵子树内,就肯定是在这棵子树的重心和i的连线上。如果是在i的上面,就肯定在fai的重心和i的连线上。于是二分答案然后通过子树重量判断就好。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500050
#define M 19
#define ll long long
int fa[N][M],h[N],ma[N][2],v[N],fi[N],c[N*2][2],li[N],n,m,ss=1;
ll cnt[N][2],Ans[N][2],Cnt[N],ans,Aha;int la[N];
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;
 }
void Get()
 {
 	int le=1,ri=1;li[1]=1;h[1]=1;
 	for (;le<=ri;le++)
 	 for (int i=fi[li[le]];i;i=c[i][1])
 	  if (c[i][0]!=fa[li[le]][0])
 	  	fa[c[i][0]][0]=li[le],h[li[++ri]=c[i][0]]=h[li[le]]+1;
 	return;
 }
void DFS()
 {
 	for (int t=n;t>=1;t--) {
 	int x=li[t];cnt[x][0]=v[x];
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x][0])
 	  {
 	  	 cnt[x][0]+=cnt[c[i][0]][0];
 	  	 cnt[x][1]+=cnt[c[i][0]][0]+cnt[c[i][0]][1];
 	  	 if (cnt[c[i][0]][0]>=cnt[ma[x][0]][0])
 	  	   ma[x][1]=ma[x][0],ma[x][0]=c[i][0]; else
 	  	 if (cnt[c[i][0]][0]>=cnt[ma[x][1]][0])
 	  	   ma[x][1]=c[i][0];
 	  }
 	if (ma[x][0]&&cnt[ma[x][0]][0]*2>=cnt[x][0])
 	 {
 	 	Ans[x][0]=Ans[ma[x][0]][0];
 	 	Ans[x][1]=Ans[ma[x][0]][1]+cnt[x][1]-cnt[ma[x][0]][1]-
 	 	  cnt[ma[x][0]][0]+(cnt[x][0]-cnt[ma[x][0]][0])*
 	 	  (h[Ans[x][0]]-h[x]);
 	 	while (cnt[Ans[x][0]][0]*2<cnt[x][0])
 	 	  Ans[x][1]+=2*cnt[Ans[x][0]][0]-cnt[x][0],
 	 	  Ans[x][0]=fa[Ans[x][0]][0];
 	 } else Ans[x][0]=x,Ans[x][1]=cnt[x][1];
 	}
 	return;
 }
inline ll min(ll x,ll y)
 {return x<y?x:y;}
void DSF()
 {
 	for (int t=1;t<=n;t++) {
 	int x=li[t];
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x][0])
 	   Cnt[c[i][0]]=Cnt[x]-2*cnt[c[i][0]][0]+Aha;
 	 }
 	return;
 }
int LCA(int x,int y)
 {
 	if (h[x]<h[y]) swap(x,y);
 	for (int i=M-1;i>=0;i--)
 	 if (h[fa[x][i]]>=h[y]) x=fa[x][i];
 	if (x!=y)
 	 {
 	 	for (int i=M-1;i>=0;i--)
 	 	 if (fa[x][i]!=fa[y][i])
 	 	   x=fa[x][i],y=fa[y][i];
 	 	x=fa[x][0];
 	 }
 	return x;
 }
int Up(int x,int y,ll z,ll o)
 {
 	if (x!=y&&(cnt[x][0]+o)*2>=z) return x;
 	for (int i=M-1;i>=0;i--)
 	 if (fa[x][i]&&(cnt[fa[x][i]][0]+o)*2<z) x=fa[x][i];
 	return h[x]-1>h[y]?fa[x][0]:0;
 }
void DFF()
 {
 	for (int t=1;t<=n;t++) {
 	int x=li[t],y=la[x];
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x][0])
 	  {
 	 	 ll k=Aha-cnt[c[i][0]][0],l=0,Tot=0;int e=0;
 	 	 if ((Aha-cnt[x][0])*2>=k) l=-1; else
 	 	  if (cnt[ma[x][0]][0]*2>=k&&ma[x][0]!=c[i][0])
 	 	    l=ma[x][0]; else
 	 	   if (ma[x][1]&&cnt[ma[x][1]][0]*2>=k&&
 	 	   	 ma[x][1]!=c[i][0]) l=ma[x][1];
 	 	 if (!l)
 	 	   e=x,Tot=Cnt[x]-cnt[c[i][0]][1]-cnt[c[i][0]][0]; else
 	 	 if (l>0)
 	 	   e=Up(Ans[l][0],x,k,0),
 	 	   Tot=Cnt[e]-cnt[c[i][0]][1]-
 	 	   	 cnt[c[i][0]][0]*(1+h[e]-h[x]); else
 	 	    {
 	 	    	l=LCA(y,x);ll tot=0;e=Up(y,l,k,0);
 	 	    	if (!e)
 	 	    	  e=Up(x,fa[l][0],k,-cnt[c[i][0]][0]),
 	 	    	  Tot=Cnt[e]-cnt[c[i][0]][1]-cnt[c[i][0]][0]*
 	 	    	  (h[c[i][0]]-h[e]); else
                  Tot=Cnt[e]-cnt[c[i][0]][1]-cnt[c[i][0]][0]*
                   (h[e]+h[c[i][0]]-2*h[l]);
 	 	    }
 	 	 ans=min(ans,Tot+Ans[c[i][0]][1]);
 	 	 la[c[i][0]]=e;
 	  }
 	 }
 	return;
 }
void Solve()
 {
 	Get();DFS();
 	for (int i=1;i<M;i++)
 	 for (int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
 	Cnt[1]=cnt[1][1];DSF();DFF();
  	return;
 }
int main()
 {
 	n=Read();
 	for (int i=1;i<n;i++) Line(Read(),Read());
 	for (int i=1;i<=n;i++) Aha+=(v[i]=Read());
 	ans=1LL << 60;Solve();
    cout <<ans<<endl;
 	return 0;
 }

HDU5574 [ACM 2015 Shanghai]:Colorful Tree

DFS序建线段树,两棵线段树分别维护答案和标记个数。设一个点的颜色为它上面第一个标记的颜色。每次相当于添加一个标记以及将子树内所有标记删除。于是考虑删除一个标记对答案的影响:如果子树内还有同色标记无影响,否则其直到与其DFS序相邻的两个标记的最深LCA的路径上面的答案-1,这东西树剖维护即可。添加标记同理,只不过子树内所有点答案赋为1。复杂度两个log。课件上面这么写的。。后来写了之后才发现只考虑最近的两个标记是有问题的。如果一个点祖先也有同色标记,那么标记下面到修改点的路径上面就会答案加一。但其实是最深同色点到修改点的路径上面答案加一。同时还要考虑DFS序相邻的两个点。所以应该修改的路径应该是原来求的东西和最深祖先同色点中的最深点,这东西用set维护一下就好。这部分复杂度也是两个log。我的写法应该是最丑的吧。。

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;
#define N 100050
int rf[N],c[N*2][2],fa[N],fi[N],mark[N],li[N],sg[N][2],h[N];
int ms[N*4],cs[N*4],ad[N*4],s[N],v[N],n,m,ss,st,t;bool xg[N*4];
multiset <int> ne[N],Mark;bool Flag;
set <int> :: iterator it;
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;
 }
void DFS(int x)
 {
 	h[x]=h[fa[x]]+1;s[x]=1;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x])
 	   fa[c[i][0]]=x,DFS(c[i][0]),s[x]+=s[c[i][0]];
 	return;
 }
void DSF(int x,int y)
 {
 	rf[x]=y;int k=0;li[sg[x][0]=++st]=x;
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x]&&s[c[i][0]]>s[k]) k=c[i][0];
 	if (k) DSF(k,y);
 	for (int i=fi[x];i;i=c[i][1])
 	 if (c[i][0]!=fa[x]&&c[i][0]!=k) DSF(c[i][0],c[i][0]);
 	sg[x][1]=st;
 	return;
 }
inline void xgj(int x,int y,int z)
 {
 	int j=z << 1;
 	if (!xg[z]) return;
 	if (x!=y)
 	 for (int i=0;i<2;i++)
 	   ad[j+i]=false,xg[j+i]=true; else cs[z]=1;
 	xg[z]=false;return;
 }
inline void adj(int x,int y,int z)
 {
 	int j=z << 1;
 	if (!ad[z]) return;
 	if (x!=y)
 	  ad[j]+=ad[z],ad[j+1]+=ad[z]; else cs[z]+=ad[z];
 	ad[z]=0;return;
 }
int Query(int x,int y,int z,int o)
 {
 	int i=x + y >> 1,j=z << 1;
 	xgj(x,y,z);adj(x,y,z);
 	if (x==y) return cs[z];
 	if (o<=i) return Query(x,i,j,o); else
 	  return Query(i+1,y,j+1,o);
 }
void Insert(int x,int y,int z,int o)
 {
 	int i=x + y >> 1,j=z << 1;ms[z]++;
 	if (x==y) return;
 	if (o<=i) Insert(x,i,j,o); else Insert(i+1,y,j+1,o);
 	return;
 }
void Add(int x,int y,int z,int o,int p,int u)
 {
 	int i=x + y >> 1,j=z << 1;
 	xgj(x,y,z);adj(x,y,z);
 	if (x==o&&y==p) {ad[z]=u;adj(x,y,z);return;}
 	if (p<=i) Add(x,i,j,o,p,u); else
 	 if (o>i) Add(i+1,y,j+1,o,p,u); else
 	   Add(x,i,j,o,i,u),Add(i+1,y,j+1,i+1,p,u);
 	return;
 }
void Modify(int x,int y,int z,int o,int p)
 {
 	int i=x + y >> 1,j=z << 1;
 	xgj(x,y,z);adj(x,y,z);
 	if (x==o&&y==p) {xg[z]=true;xgj(x,y,z);return;}
 	if (p<=i) Modify(x,i,j,o,p); else
 	 if (o>i) Modify(i+1,y,j+1,o,p); else
 	   Modify(x,i,j,o,i),Modify(i+1,y,j+1,i+1,p);
 	return;
 }
void Increase(int x,int y,int z)
 {
 	while (rf[x]!=rf[y])
 	  Add(1,n,1,sg[rf[x]][0],sg[x][0],z),x=fa[rf[x]];
 	Add(1,n,1,sg[y][0],sg[x][0],z);
 	return;
 }
int LCA(int x,int y)
 {
 	int lx=0;
 	while (rf[x]!=rf[y])
 	 {
 	 	bool flag=false;
 	 	if (h[rf[y]]>h[rf[x]]) swap(x,y),flag=true;
 	 	x=rf[x];if (!flag) lx=x;x=fa[x];
 	 	if (flag) swap(x,y);
 	 }
 	if (h[x]<=h[y]) return lx; else return li[sg[y][0]+1];
 }
inline int Lower(int x,int y)
 {return x==-1||h[x]<h[y]?y:x;}
int Get(int x,int y)
 {
 	int k=-1,l=x,e;
 	while (l)
 	 {
 	 	it=ne[y].lower_bound(sg[l][0]+1);
 	 	if (it!=ne[y].begin())
 	 	 if (*(--it)!=sg[x][0]) it++;
 	 	if (it!=ne[y].begin()&&(*(--it)>=sg[rf[l]][0]))
 	 	  {k=li[*it];break;}
 	 	l=fa[rf[l]];
 	 }
 	if (k==-1) return k;l=e=x;
 	while (l)
 	 {
 	 	it=Mark.lower_bound(rf[l]==rf[k]?sg[k][0]+1:sg[rf[l]][0]);
 	 	if (it!=Mark.end()&&*it<=sg[l][0]) e=li[*it];
 	 	if (rf[l]==rf[k]) break;
 	 	l=fa[rf[l]];
 	 }
 	return e;
 }
void Pop(int x,int y)
 {
 	if (!mark[x]) return;
 	Mark.erase(sg[x][0]);int k=Get(x,y);
 	it=ne[y].lower_bound(sg[x][0]);
 	if (it!=ne[y].begin()) k=Lower(k,LCA(x,li[*(--it)])),it++;
 	if (++it!=ne[y].end())
 	 {
 	 	int l=*it;
 	 	if (sg[li[l]][1]<=sg[x][1]) {it--;ne[y].erase(it);return;}
 	 	k=Lower(k,LCA(x,li[l]));
 	 }
 	it--;ne[y].erase(it);
 	Increase(x,k==-1?1:k,-1);
 	return;
 }
void Push(int x,int y)
 {
 	Insert(1,n,1,sg[x][0]);ne[y].insert(sg[x][0]);
 	int k=Get(x,y);Mark.insert(sg[x][0]);
 	it=ne[y].lower_bound(sg[x][0]);
 	if (it!=ne[y].begin()) k=Lower(k,LCA(x,li[*(--it)])),it++;
 	if (++it!=ne[y].end())
 	 {
 	 	int l=*it;
 	 	if (sg[li[l]][1]<=sg[x][1]) return;
 	 	k=Lower(k,LCA(x,li[l]));
 	 }
 	Increase(x,k==-1?1:k,1);
 	return;
 }
void Delete(int x,int y,int z,int o,int p)
 {
 	int i=x + y >> 1,j=z << 1;
 	if (!ms[z]) return;
 	if (x==y) {Pop(li[x],mark[li[x]]);mark[li[x]]=ms[z]=0;return;}
 	if (p<=i) Delete(x,i,j,o,p); else
 	 if (o>i) Delete(i+1,y,j+1,o,p); else
 	   Delete(x,i,j,o,i),Delete(i+1,y,j+1,i+1,p);
 	ms[z]=ms[j]+ms[j+1];
 	return;
 }
void Gay_a_wave(int y,int x)
 {
 	Delete(1,n,1,sg[x][0],sg[x][1]);
 	Push(x,y);mark[x]=y;Modify(1,n,1,sg[x][0],sg[x][1]);
 }
void Pretreat()
 {
 	DFS(1);DSF(1,1);
 	for (int i=1;i<=n;i++) Gay_a_wave(v[li[i]],li[i]);
 	return;
 }
void Clear(int x,int y,int z)
 {
 	int i=x + y >> 1,j=z << 1;
 	cs[z]=ms[z]=xg[z]=ad[z]=false;
 	if (x!=y) Clear(x,i,j),Clear(i+1,y,j+1);
 }
int main()
 {
 	t=Read();
 	for (int T=1;T<=t;T++)
 	 {
 	 	printf("Case #%d:\n",T);
 	 	n=Read();ss=1;st=0;
 	 	for (int i=1;i<n;i++) Line(Read(),Read());
 	 	for (int i=1;i<=n;i++) v[i]=Read();
 	 	Pretreat();m=Read();Flag=true;
 	    for (int i=1;i<=m;i++)
 	     if (Read())
 	       printf("%d\n",Query(1,n,1,sg[Read()][0])); else
 	       Gay_a_wave(Read(),Read());
 	    for (int i=1;i<=n;i++)
 	      fi[i]=mark[i]=false,ne[i].clear();
 	    Mark.clear();Clear(1,n,1);
 	 }
 	return 0;
 }

BZOJ2957

之前不知为何记得这个是树套树好题于是抽空做了一下。思索很久无果。

感觉倒是线段树还有分块做法一下就想出来了。。(其实线段树做法是因为刚好做过一道差不多的题才会做= =)

线段树做法很优美啊:

维护每段区间的答案。还有这个答案的右端点。

Update的时候套个询问就好了。具体可以看这里

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100050
double bd[N*4];int Ans[N*4],n,m;
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 double max(double x,double y)
 {return x<y?y:x;}
int Query(int x,int y,int z,double o)
 {
 	int i=x + y >> 1,j=z << 1;
 	if (x==y) return bd[z]>o;
 	if (bd[j]<=o) return Query(i+1,y,j+1,o); else
 	  return Ans[z]-Ans[j]+Query(x,i,j,o);
 }
void Modify(int x,int y,int z,int o,double p)
 {
 	int i=x + y >> 1,j=z << 1;
 	if (x==y) {Ans[z]=1;bd[z]=p;return;}
 	if (o<=i) Modify(x,i,j,o,p); else
 	  Modify(i+1,y,j+1,o,p);
 	bd[z]=max(bd[j],bd[j+1]);
 	Ans[z]=Ans[j]+Query(i+1,y,j+1,bd[j]);
 	return;
 }
int main()
 {
 	n=Read();m=Read();
 	while (m--)
 	 {
 	 	int k=Read(),l=Read();Modify(1,n,1,k,l*1.0/k);
 	 	printf("%d\n",Ans[1]);
 	 }
 	return 0;
 }

POI21填坑计划

[Upd 12.24]:因为校内集训先坑在这里好了。。感觉剩下的题目好难啃。。

开新坑辣!先口胡一波再写好了。。

现在完成了:

15

[Couriers]:无脑主席树,当然也可以莫队

[Hotel]:无脑DP+乱搞。

[Salad Bar]:O(n log n)的感觉比较无脑。。不知道有没有O(n)的。。

[Around the world]:每次询问任意固定一个起点,然后O(n)求出每个点往左往右走到这个起点的步数和最后一步的距离,最后再看最后一步的距离能否两步缩成一步。O(nm)

[Bricks]:差不多大于1/2就不能放?感觉好想好证好构造。因为固定首尾所以多判几种情况乱搞搞就好了?

[Card]:拿棵线段树随便维护一下就好?反正一段区间只会有四种情况

[FarmCraft]:树形DP+SB贪心?

[Little Bird]:首先一段区间所包含的劳累值肯定是连续的。然后就每个值按高度维护一个单调队列以及维护一下这段区间内的劳累值区间左右端点。然后每次删除一个点就只要在单调队列里面删除。算当前劳累值就只要从最小劳累值和次小劳累值转移就好了。

[Solar Panels]:分成两种情况,第一种答案小于sqrt(1e9),直接枚举判断就好。第二种n/gcd或者m/gcd小于sqrt(1e9),那么设n/gcd=k,则gcd肯定等于[maxn/k],然后按照m范围判断即可。因为不一定是n碰到上界所以m再来一遍即可。(因为两个都没有碰到上界的话gcd是可以加一的)复杂度O(sqrt(1e9)*t)

按照BZOJ上面的AC人数,貌似水题全都写完了。。好虚啊。。

[Solar Lamps]:把一个角度放大CF有一个题也用到过,其它部分直接上个树套树就好了?特判掉范围是一条线的情况就好。

[Rally]:之前想了一个做法发现是在瞎BB。堆+拓扑排序。。主要是一直在怎么找必经点而不是在维护答案上面想所以并不会做,而且答案是维护的一个割集的而不是维护整张图。智商是硬伤。。

[SuperComputer]:还是不会。。听说ans=max(i+[sum[i]/k])= =证明在这里。虽然想过类似结论但是还是没想到这个东西= =太弱= =。然后就可以斜率优化了。

[Criminals]:之前一直看漏了一个条件发现是神题不会做= =后来发现直接扫一遍求出每个点往两个方向的最短可以匹配的序列是在哪个位置就好了。。

[Ant colony]:之前一直没看懂题。。原来是每个叶子节点都会有。。只要处理出每个叶子节点的被除数是多少然后对询问还有这东西排序扫一遍就好了。。

[Freight]:找到一个并没很大用的性质,往那方面想了一个从后往前的贪心,但是明显前面的发车状态会对后面的贪心策略造成影响,于是还没写就弃疗了。后来找到另外一个比较显然的性质就是如果当前在回程的话就应该把所有在T的点全部回到S。因为这样最多会把后面的车推迟s分钟。但是如果这s辆车扣在这里等最后才放的话也要推迟s分钟。于是肯定是如果放车就都放掉比较好。于是可以设t[i]代表第i辆车作为那次回程的最后一辆车回到S的时间是多少。则我们从j<i转移。分两种情况:t[j]+i-j-1<=T[i]或者大于。首先t[j]肯定是单调递增的所以t[j]-j肯定单调不减,并且分界线肯定也是单调不减的。第一种情况t[i]=min(T[i]+s*2+i-j-1),直接取最后一个即可。第二种情况t[i]=min(t[j]+(i-j-1+s)*2),所以维护一棵线段树查询区间最小值即可。至于时间重合的情况直接预处理T[i]=max(T[i],T[i-1]+1)

[Snake]:感觉像是某种神奇的大讨论。。不会啊。。

[Tourism]:跪Claris神脑洞。

UOJ#132 小园丁与老司机

由于代码能力拙计,一直很想写这题,于是学了上下界网络流之后就开始写这题了。

感觉理清了思路没有想象中难写。但是感觉要在考场上面写出来确实比较厉害。。

首先第一问DP做法显然。第二问下界最小流有特殊的建图方式然后跑两遍Dinic就好了。。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
#define N 50050
#define M 2000050
#define INF 0x3f7f7f7f
int sg[N],wz[N][2],dir[N][3],fi[N],c[M*2][3],Trs[N];
int ss=1,st,n,m,S=N-1,T=N-2,_S=N-3,_T=N-4,ans;
int Ans[N],cur[N],Wz[N][2],sign[N],ma[N],la[N],h[N];
queue <int> li;bool b[N],flag[N],vis[N];
inline int Read()
 {
 	int x=0;char y;bool z=0;
 	do y=getchar(),z|=y=='-'; while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return z?-x:x;
 }
inline void Line(int x,int y,int z)
 {
 	c[++ss][0]=y;c[ss][1]=fi[x];c[ss][2]=z;fi[x]=ss;
 	c[++ss][0]=x;c[ss][1]=fi[y];c[ss][2]=0;fi[y]=ss;
 }
inline bool cmp0(int x,int y)
 {return wz[x][0]<wz[y][0]||(wz[x][0]==wz[y][0]&&wz[x][1]<wz[y][1]);}
inline bool cmp1(int x,int y)
 {return Wz[x][0]<Wz[y][0]||(Wz[x][0]==Wz[y][0]&&wz[x][1]<wz[y][1]);}
inline bool cmp2(int x,int y)
 {return Wz[x][1]<Wz[y][1]||(Wz[x][1]==Wz[y][1]&&wz[x][1]<wz[y][1]);}
inline bool cmp(int x,int y)
 {return wz[x][1]>wz[y][1]||(wz[x][1]==wz[y][1]&&wz[x][0]<wz[y][0]);}
void Up(int x)
 {
 	if (!x) return;
 	if (x!=n) printf("%d ",x);
 	if (!la[x]) Up(dir[x][Trs[x]]); else
 	 {
 	 	int k=sign[x],l=sign[la[x]],e;
 	 	if (k<l)
 	 	 {
 	 	 	e=k;
 	 	 	while (k-1&&wz[sg[k-1]][1]==wz[sg[k]][1])
 	 	 	  printf("%d ",sg[--k]);
 	 	 	k=e+1;
 	 	 	for (;k<=l;k++) printf("%d ",sg[k]);
 	 	 } else
 	 	 {
 	 	 	e=k;
 	 	 	while (k<n&&wz[sg[k+1]][1]==wz[sg[k]][1])
 	 	 	  printf("%d ",sg[++k]);
 	 	 	k=e-1;
 	 	 	for (;k>=l;k--) printf("%d ",sg[k]);
 	 	 }
 	 	Up(dir[la[x]][Trs[la[x]]]);
 	 }
 	return;
 }
void DP()
 {
 	for (int i=1;i<=n;i++)
 	  Wz[i][0]=wz[i][0]+wz[i][1],
 	  Wz[i][1]=wz[i][0]-wz[i][1];
 	sort(sg+1,sg+n+1,cmp0);
 	for (int i=1;i<=n;i++)
 	 while (i<n&&wz[sg[i+1]][0]==wz[sg[i]][0])
 	   i++,dir[sg[i-1]][1]=sg[i];
 	sort(sg+1,sg+n+1,cmp1);
 	for (int i=1;i<=n;i++)
 	 while (i<n&&Wz[sg[i+1]][0]==Wz[sg[i]][0])
 	   i++,dir[sg[i-1]][0]=sg[i];
 	sort(sg+1,sg+n+1,cmp2);
 	for (int i=1;i<=n;i++)
 	 while (i<n&&Wz[sg[i+1]][1]==Wz[sg[i]][1])
 	   i++,dir[sg[i-1]][2]=sg[i];
 	sort(sg+1,sg+n+1,cmp);
 	for (int i=1;i<=n;i++) sign[sg[i]]=i;
//la是从哪里过来,Trs只能从上面过来,ma是当前距离,Ans是答案距离
 	for (int i=1;i<=n;)
 	 {
 	 	int ri=i;
 	 	while (ri<n&&wz[sg[ri+1]][1]==wz[sg[ri]][1]) ri++;
 	 	for (int j=i;j<=ri;j++)
 	 	 for (int k=0;k<3;k++)
 	 	  {
 	 	  	 int l=Ans[dir[sg[j]][k]];
 	 	  	 if (l>ma[sg[j]])
 	 	  	   ma[sg[j]]=Ans[sg[j]]=l,Trs[sg[j]]=k;
 	 	  }
 	 	int Ma=0;
 	 	for (int j=i;j<=ri;j++)
 	 	 {
 	 	 	if (Ma&&ri-Ma+ma[sg[Ma]]>Ans[sg[j]])
 	 	 	  Ans[sg[j]]=ri-Ma+ma[sg[Ma]],la[sg[j]]=sg[Ma];
 	 	 	if (!Ma||ri-j+ma[sg[j]]>ri-Ma+ma[sg[Ma]]) Ma=j;
 	 	 }
 	 	Ma=0;
 	 	for (int j=ri;j>=i;j--)
 	 	 {
 	 	 	if (Ma&&Ma-i+ma[sg[Ma]]>Ans[sg[j]])
 	 	 	  Ans[sg[j]]=Ma-i+ma[sg[Ma]],la[sg[j]]=sg[Ma];
 	 	 	if (!Ma||j-i+ma[sg[j]]>Ma-i+ma[sg[Ma]]) Ma=j;
 	 	 }
 	 	for (;i<=ri;i++) Ans[sg[i]]++;
 	 }
 	cout <<Ans[n]-1<<endl;Up(n);puts("");
 	return;
 }
bool BFS()
 {
 	memset(h,0,sizeof(h));
 	for (int i=1;i<=n;i++) cur[i]=fi[i];
 	for (int i=_T;i<N;i++) cur[i]=fi[i];
 	int le=1,ri=1;h[_S]=1;li.push(_S);
    while (!li.empty())
     {
     	int k=li.front();li.pop();
     	for (int i=fi[k];i;i=c[i][1])
     	 if (c[i][2]&&!h[c[i][0]])
     	   h[c[i][0]]=h[k]+1,li.push(c[i][0]);
     }
    return h[_T]>0;
 }
int DFS(int x,int y)
 {
 	int k,l=0;
 	if (x==_T) return y;
 	for (int i=cur[x];i&&y;i=c[i][1])
 	 if (c[i][2]&&h[c[i][0]]==h[x]+1)
 	  {
 	  	 k=DFS(c[i][0],min(y,c[i][2]));cur[x]=i;
 	  	 if (k) l+=k,y-=k,c[i][2]-=k,c[i^1][2]+=k;
 	  }
 	return l;
 }
inline void line(int x,int y)
 {Line(x,y,INF);Line(_S,y,1);Line(x,_T,1);flag[y]=true;}
void Trans(int x)
 {
 	if (vis[x]) return;vis[x]=true;
 	for (int i=0;i<3;i++)
 	 if (ma[x]==Ans[dir[x][i]]&&dir[x][i]) line(x,dir[x][i]);
 }
void Clear()
 {while (!li.empty()) li.pop();}
void Build()
 {
 	flag[n]=true;
 	for (int i=n;i;)
 	 {
 	 	int le=i,Ma=0;
 	 	while (le>1&&wz[sg[le-1]][1]==wz[sg[i]][1]) le--;
 	 	for (int j=le;j<=i;j++)
 	 	 {
 	 	 	if (flag[sg[j]])
 	 	 	 {
 	 	 	 	if (!la[sg[j]]) Trans(sg[j]);
 	 	 	 	if (Ma==Ans[sg[j]])
 	 	 	 	 while (!li.empty())
 	 	 	  	   Trans(li.front()),li.pop();
 	 	 	 }
 	 	 	if (ma[sg[j]]+i-j+1>Ma)
 	 	 	  Clear(),li.push(sg[j]),Ma=ma[sg[j]]+i-j+1; else
 	 	 	if (ma[sg[j]]+i-j+1==Ma)
 	 	 	  li.push(sg[j]);
 	 	 }
 	 	Ma=0;Clear();
 	 	for (int j=i;j>=le;j--)
 	 	 {
 	 	 	if (flag[sg[j]]&&Ma==Ans[sg[j]])
 	 	 	 while (!li.empty())
 	 	 	   Trans(li.front()),li.pop();
 	 	 	if (ma[sg[j]]+j-le+1>Ma)
 	 	 	  Clear(),li.push(sg[j]),Ma=ma[sg[j]]+j-le+1; else
 	 	 	if (ma[sg[j]]+j-le+1==Ma)
 	 	 	  li.push(sg[j]);
 	 	 }
 	 	i=le-1;
 	 }
 	return;
 }
void Flow()
 {
 	for (int i=1;i<=n;i++)
 	  Line(S,i,INF),Line(i,T,INF);
 	Build();
 	while (BFS()) DFS(_S,INF);
 	Line(T,S,INF);
 	while (BFS()) DFS(_S,INF);
 	cout <<c[ss][2]<<endl;
 	return;
 }
int main()
 {
 	n=Read()+1;
 	for (int i=1;i<n;i++)
 	  wz[sg[i]=i][0]=Read(),wz[i][1]=Read();sg[n]=n;
 	DP();Flow();
    return 0;
 }