发表于 | 更新于

点对之间不同的最小割至多有n−1n-1种 求一遍最小割，然后继续分治处理S\T集合 ZJOI 2011 最小割 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include "lucida"
using std::fill;
using std::copy;
const int MAXN=150+11,MAXM=3000+11,INF=INT_MAX;
struct Edge *Edge_Pool,*Edge_Me;
struct Edge {
	int to,cap,v;
	Edge *pre,*rev;
	Edge(int to,int cap,Edge *pre):to(to),cap(cap),v(0),pre(pre) {}
	void *operator new(size_t) {
		return Edge_Me++;
	}
}*G[MAXN]={Edge_Pool=Edge_Me=alloc(Edge,MAXM<<1)};int n;
void Reset() {
	for(int pos=1;pos<=n;++pos)
		for(Edge *e=G[pos];e;e=e->pre)
			e->v=0;
}
namespace isap {
	Edge *pree[MAXN],*arc[MAXN];
	int num[MAXN],d[MAXN];
	int Aug(int t) {
		int minf=INF;
		for(Edge *e=pree[t];e;e=pree[e->rev->to])
			chkmn(minf,e->cap-e->v);
		for(Edge *e=pree[t];e;e=pree[e->rev->to]) {
			e->v+=minf;
			e->rev->v-=minf;
		}
		return minf;
	}
	int ISAP(int s,int t) {
		pree[s]=0;
		fill(d+1,d+1+n,0);
		fill(num+1,num+1+n,0);
		copy(G+1,G+1+n,arc+1);
		num[0]=n;
		int flow=0;
		for(int cp=s;d[s]<n;cp=cp==t?(flow+=Aug(t),s):cp) {
			bool adv=0;
			for(Edge *&e=arc[cp];e;e=e->pre)
				if(e->cap>e->v && d[e->to]+1==d[cp]) {
					adv=1;
					pree[cp=e->to]=e;
					break;
				}
			if(!adv) {
				if(!--num[d[cp]])
					break;
				d[cp]=n;
				for(Edge *e=(arc[cp]=G[cp]);e;e=e->pre)
					if(e->cap>e->v) chkmn(d[cp],d[e->to]+1);
				++num[d[cp]];
				if(cp!=s) cp=pree[cp]->rev->to;
			}
		}
		return flow;
	}
}using isap::ISAP;
void Adde(int f,int t,int cap) {
	G[f]=new Edge(t,cap,G[f]);
	G[t]=new Edge(f,cap,G[t]);
	G[f]->rev=G[t];G[t]->rev=G[f];
}
int minCut[MAXN][MAXN],set[MAXN];
bool ud[MAXN];
void DFS(int pos) {
	ud[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->cap>e->v && !ud[e->to])
			DFS(e->to);
}
void DC(int l,int r) {
	if(l==r) return;
	Reset();
	int flow=ISAP(set[l],set[r]);
	fill(ud+1,ud+1+n,0);
	DFS(set[l]);
	for(int i=1;i<=n;++i) if(ud[i])
		for(int j=1;j<=n;++j) if(!ud[j])
			minCut[j][i]=(chkmn(minCut[i][j],flow),minCut[i][j]);
	static int pset[MAXN];
	int pl=l,pr=r;
	for(int i=l;i<=r;++i)
		pset[ud[set[i]]?pl++:pr--]=set[i];
	copy(pset+l,pset+r+1,set+l);
	DC(l,pl-1);DC(pr+1,r);
}
void Work() {
	Edge_Me=Edge_Pool;
	memset(G,0,sizeof(G));
	int m,Q;is>>n>>m;
	for(int i=1;i<=m;++i) {
		int u,v,c;is>>u>>v>>c;
		Adde(u,v,c);
	}
	for(int i=1;i<=n;++i) {
		set[i]=i;
		fill(minCut[i]+1,minCut[i]+1+n,INF);
	}
	DC(1,n);
	is>>Q;
	for(int loop=1;loop<=Q;++loop) {
		int x;is>>x;
		int Ans=0;
		for(int i=1;i<n;++i)
			for(int j=i+1;j<=n;++j)
				Ans+=minCut[i][j]<=x;
		os<<Ans<<'\n';
	}
}
int main() {
//	freopen("input","r",stdin);
	int T;is>>T;
	while(T--) {
		Work();
		if(T) os<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution

因为询问的是不覆盖一个点的路径 那么就把修改也转化成补集，可以通过树剖DFS序解决 感觉并不是很难想，但就是想不到。。树剖DFS序看起来有无限可能。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include "lucida"

using std::priority_queue;
using std::swap;
using std::sort;
using std::pair;
const int MAXN=1e5+11,MAXM=2e5+11;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
struct MagicHeap {
	priority_queue<int> app,rmv;
	void Maintain() {
		while(!app.empty() && !rmv.empty() && app.top()==rmv.top()) {
			app.pop();
			rmv.pop();
		}
	}
	int Top() {
		Maintain();
		return !app.empty()?app.top():-1;
	}
	void Push(int x) {
		Maintain();
		app.push(x);
	}
	void Remove(int x) {//app中必须有!
		Maintain();
		rmv.push(x);
	}
};
namespace segtree {
	struct Node {
		Node *son[2];
		MagicHeap heap;
		Node() {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN<<2);
			return Me++;
		}
	};
	struct SegTree {
		Node *root;
		int L,R;
		void Build(Node *&pos,int L,int R) {
			pos=new Node;
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
			}
		}
		void Edit(Node *pos,int L,int R,int l,int r,int v) {
			if(l<=L && R<=r)
				v>0?pos->heap.Push(v):pos->heap.Remove(-v);
			else {
				int Mid=(L+R)>>1;
				if(l<=Mid) Edit(pos->son[0],L,Mid,l,r,v);
				if(Mid+1<=r) Edit(pos->son[1],Mid+1,R,l,r,v);
			}
		}
		int Access(Node *pos,int L,int R,int goal) {
			int res=pos->heap.Top();
			if(L!=R) {
				int Mid=(L+R)>>1;
				if(goal<=Mid) chkmx(res,Access(pos->son[0],L,Mid,goal));
				else chkmx(res,Access(pos->son[1],Mid+1,R,goal));
			}
			return res;
		}
		SegTree() {}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		void Edit(int l,int r,int v) {//正数插入 负数删除相反数
			if(l<=r) Edit(root,L,R,l,r,v);
		}
		int Query(int pos) {
			return Access(root,L,R,pos);
		}
	};
}using segtree::SegTree;
namespace divide {
	SegTree seg;
	int cht[MAXN],dep[MAXN],sz[MAXN],fa[MAXN],prefer[MAXN],dfs[MAXN],lbd[MAXN],rbd[MAXN],dc;
	void DFS(int pos) {
		sz[pos]=1;dep[pos]=dep[fa[pos]]+1;
		for(Edge *e=G[pos];e;e=e->pre)
			if(fa[pos]!=e->to) {
				int u=e->to;
				fa[u]=pos;
				DFS(u);
				sz[pos]+=sz[u];
				if(sz[u]>=sz[prefer[pos]]) prefer[pos]=u;
			}
	}
	void Assign(int pos,int top) {
		cht[pos]=top;
		dfs[++dc]=pos;
		lbd[pos]=dc;
		if(prefer[pos]) {
			Assign(prefer[pos],top);
			for(Edge *e=G[pos];e;e=e->pre)
				if(e->to!=fa[pos] && e->to!=prefer[pos]) {
					int u=e->to;
					Assign(u,u);
				}
		}
		rbd[pos]=dc;
	}
	void Divide() {
		DFS(1);
		Assign(1,1);
		new(&seg) SegTree(1,dc);
	}
	void CpChain(int p1,int p2,int v) {
		static pair<int,int> range[MAXN];
		int rc=0;
		while(cht[p1]!=cht[p2]) {
			if(dep[cht[p1]]<dep[cht[p2]]) swap(p1,p2);
			range[++rc]=pair<int,int>(lbd[cht[p1]],lbd[p1]);
			p1=fa[cht[p1]];
		}
		if(dep[p1]>dep[p2]) swap(p1,p2);
		range[++rc]=pair<int,int>(lbd[p1],lbd[p2]);
		sort(range+1,range+1+rc);
		seg.Edit(1,range[1].first-1,v);
		for(int i=2;i<=rc;++i)
			seg.Edit(range[i-1].second+1,range[i].first-1,v);
		seg.Edit(range[rc].second+1,dc,v);//没有判后面这一部分
	}
	int Query(int x) {
		return seg.Query(lbd[x]);
	}
}using namespace divide;

int main() {
//	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	for(int i=1;i<=n-1;++i)	{
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	Divide();
	static struct {int a,b,v;}op[MAXM];
	for(int i=1;i<=m;++i) {
		int opt,t,x;is>>opt;
		switch(opt) {
			case 0:
				is>>op[i].a>>op[i].b>>op[i].v;
				CpChain(op[i].a,op[i].b,op[i].v);
				break;
			case 1:
				is>>t;
				CpChain(op[t].a,op[t].b,-op[t].v);
				break;
			case 2:
				is>>x;
				os<<Query(x)<<'\n';
				break;
		}
	}
	return 0;
}

发表于 | 更新于

Link

Sengxian大神给出的做法，说实话，确实比Po姐的简洁 虽然Po姐的做法非常直观，但是修改的操作的讨论太繁杂 本来想了一种自己的做法，可以按照Po姐的办法差分而又避免繁杂的讨论，写出来之后怎么也调不对 只好又去研究了一番Sengxian的题解，感觉非常喵

Solution

注意到的主要事实就是gcd(a,b)=gcd(a,b−a)\gcd(a,b)=\gcd(a,b-a)，由此就可以差分来避免区间修改。一维的做法扩展一下，最后就可以推出一个非常优美的二维做法。 Po姐的第二维可变的二维数组写法非常别致啊。。 然后细节比较多，要注意一维和二维线段树查询的边界 改成Sengxian的做法之后，一开始WA了。把二维线段树改成暴力维护矩阵，WA的一样。。 搞了一会儿没办法，把一维线段树也改成暴力了，然后就对了。。 究其原因，是因为一维线段树的边界没有考虑完全，然而一维线段树在二维线段树里是对的，是因为二维线段树的边界判全了。。 这说明，暴露在外直接面向全局的函数一定要判好边界等等特殊情况，被套在里面对了，不代表确实是对的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include "lucida"
using std::max;
using std::min;
const int MAXN=500000+11;
int n,m,X,Y;
int64 gcd(int64 a,int64 b) {
	a=a<0?-a:a;b=b<0?-b:b;
	for(int64 t;b;t=a%b,a=b,b=t);
	return a;
}
struct TwO {
	int step;
	int64 a[MAXN];
	int64 *operator [](int x) {
		return a+(x-1)*step+1;
	}
}imap;
namespace segtree1D {
	const int SIZE=(MAXN<<4)+(MAXN<<3),OPT_COVER=0,OPT_ADD=1;
	struct Node {
		Node *son[2];
		int64 v;
		Node(int64 v):v(v) {
			son[0]=son[1]=0;
		}
		void Up() {
			v=gcd(son[0]->v,son[1]->v);
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
	};
	struct SegTree {
		Node *root;int L,R;
		SegTree(){}
		void Build(Node *&pos,int L,int R,int64 a[]) {
			pos=new Node(a[L]);
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid,a);
				Build(pos->son[1],Mid+1,R,a);
				pos->Up();
			}
		}
		void Edit(Node *pos,int L,int R,int goal,int64 c,int mode) {
			if(L==R) (mode==OPT_COVER)?(pos->v=c):(pos->v+=c);
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Edit(pos->son[0],L,Mid,goal,c,mode);
				else Edit(pos->son[1],Mid+1,R,goal,c,mode);
				pos->Up();
			}
		}
		int64 Access(Node *pos,int L,int R,int l,int r) {
			if(l<=L && R<=r)
				return pos->v;
			else {
				int Mid=(L+R)>>1;
				int64 res=0;
				if(l<=Mid) res=gcd(res,Access(pos->son[0],L,Mid,l,r));
				if(Mid+1<=r) res=gcd(res,Access(pos->son[1],Mid+1,R,l,r));
				return res;
			}
		}

		SegTree(int L,int R,int64 a[]):L(L),R(R) {
			if(L<=R) Build(root,L,R,a);
		}
		SegTree(Node *root,int L,int R):root(root),L(L),R(R) {}
		void Add(int pos,int64 c) {
			if(L<=pos && pos<=R) Edit(root,L,R,pos,c,OPT_ADD);//没判pos.
		}
		void Cover(int pos,int64 c) {
			if(L<=pos && pos<=R) Edit(root,L,R,pos,c,OPT_COVER);
		}
		int64 Qgcd(int l,int r) {
			return L<=R && l<=r?Access(root,L,R,l,r):0;
		}
		int64 Qgcd(int pos) {
			return L<=R?Access(root,L,R,pos,pos):0;
		}
	};
	Node *Merge(Node *p1,Node *p2,int L,int R) {
		Node *pos=new Node(0);
		if(L==R) pos->v=gcd(p1->v,p2->v);
		else {
			int Mid=(L+R)>>1;
			pos->son[0]=Merge(p1->son[0],p2->son[0],L,Mid);
			pos->son[1]=Merge(p1->son[1],p2->son[1],Mid+1,R);
			pos->Up();
		}
		return pos;
	}
}
namespace segtree2D {
	typedef segtree1D::SegTree InnerTree;
	using segtree1D::Merge;
	const int SIZE=MAXN<<2;
	struct Node {
		Node *son[2];
		InnerTree tr;
		Node() {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
	};
	struct SegTree {
		Node *root;int L,R,IL,IR;
		SegTree(){}
		void Build(Node *&pos,int L,int R,TwO &a) {
			pos=new Node;
			if(L==R) 
				new(&pos->tr) InnerTree(IL,IR,a[L]);
			else {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid,a);
				Build(pos->son[1],Mid+1,R,a);
				new(&pos->tr) InnerTree(Merge(pos->son[0]->tr.root,pos->son[1]->tr.root,IL,IR),IL,IR);
			}
		}
		void Edit(Node *pos,int L,int R,int goal,int ig,int64 c) {
			if(L==R) 
				pos->tr.Add(ig,c);
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Edit(pos->son[0],L,Mid,goal,ig,c);
				else Edit(pos->son[1],Mid+1,R,goal,ig,c);
				pos->tr.Cover(ig,gcd(pos->son[0]->tr.Qgcd(ig),pos->son[1]->tr.Qgcd(ig)));	
			}
		}
		int64 Access(Node *pos,int L,int R,int l,int r,int il,int ir) {
			if(l<=L && R<=r)
				return pos->tr.Qgcd(il,ir);
			else {
				int Mid=(L+R)>>1;int64 res=0;
				if(l<=Mid) res=gcd(res,Access(pos->son[0],L,Mid,l,r,il,ir));
				if(Mid+1<=r) res=gcd(res,Access(pos->son[1],Mid+1,R,l,r,il,ir));
				return res;
			}
		}

		SegTree(int x1,int y1,int x2,int y2,TwO &a):L(x1),R(x2),IL(y1),IR(y2) {
			if(L<=R && IL<=IR) Build(root,L,R,a);
		}
		void Add(int x,int y,int64 c) {
			if(L<=R && IL<=IR && L<=x && x<=R && IL<=y && y<=IR) Edit(root,L,R,x,y,c);
		}
		int64 Qgcd(int x1,int y1,int x2,int y2) {
			return L<=R && IL<=IR && x1<=x2 && y1<=y2?Access(root,L,R,x1,x2,y1,y2):0;
		}
	};
}
typedef segtree1D::SegTree Axis;
typedef segtree2D::SegTree Plane;
Plane pt;Axis xt,yt;int64 origin;
void Build() {
	static TwO pdiff;
	static int64 xdiff[MAXN],ydiff[MAXN];
	pdiff.step=m;
	for(int i=1;i<=n-1;++i)
		for(int j=1;j<=m-1;++j)
			pdiff[i][j]=imap[i+1][j+1]-imap[i+1][j]-imap[i][j+1]+imap[i][j];
	for(int i=1;i<=n-1;++i)
		xdiff[i]=imap[i+1][Y]-imap[i][Y];
	for(int i=1;i<=m;++i)
		ydiff[i]=imap[X][i+1]-imap[X][i];
	origin=imap[X][Y];
	new(&xt) Axis(1,n-1,xdiff);
	new(&yt) Axis(1,m-1,ydiff);
	new(&pt) Plane(1,1,n-1,m-1,pdiff);
}
void Modify(int x1,int y1,int x2,int y2,int64 c) {
	if(x1<=X && X<=x2 && y1<=Y && Y<=y2) 
		origin+=c;
	if(y1<=Y && Y<=y2) {
		xt.Add(x1-1,c);
		xt.Add(x2,-c);
	}
	if(x1<=X && X<=x2) {
		yt.Add(y1-1,c);
		yt.Add(y2,-c);
	}
	pt.Add(x1-1,y1-1,c);
	pt.Add(x1-1,y2,-c);
	pt.Add(x2,y1-1,-c);
	pt.Add(x2,y2,c);
}
int64 Query(int x1,int y1,int x2,int y2) {
	assert(x1<=X && X<=x2 && y1<=Y && Y<=y2);
	int64 res=origin;
	res=gcd(res,xt.Qgcd(x1,x2-1));
	res=gcd(res,yt.Qgcd(y1,y2-1));
	res=gcd(res,pt.Qgcd(x1,y1,x2-1,y2-1));
	return res;
}
int main() {
//	freopen("input","r",stdin);
	is>>n>>m;imap.step=m;
	int Q;is>>X>>Y>>Q;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			is>>imap[i][j];
	Build();
	for(int i=1;i<=Q;++i) {
		int opt,x1,x2,y1,y2;int64 c;
		is>>opt>>x1>>y1>>x2>>y2;
		if(opt==0) 
			os<<Query(X-x1,Y-y1,X+x2,Y+y2)<<'\n';
		else {
			is>>c;
			Modify(x1,y1,x2,y2,c);
		}
	}
	return 0;
}

发表于 | 更新于

Link

有一种智障叫做看到了简单路径的定义就觉得需要求简单路径 有一种被欺骗叫做写挂复杂度而心甘情愿地卡了一晚上常数

Solution

所以说，暴力并查集+线段树+O(n)O(n)扫可以得到45分。。 正解是非常鬼畜的 把边按照aa排序，分成m\sqrt m块

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include "lucida"

const int MAXM=100000+11,MAXN=50000+11;
using std::max;
using std::min;
using std::swap;
using std::sort;
template <class T> inline T max(const T &a,const T &b,const T &c) {return max(a,max(b,c));}
namespace dju {
	const int PERM_OPT=0,TEMP_OPT=1;
	struct Node {
		int fa,sz,mxa,mxb;
		void Reset() {
			fa=0;
			sz=1;
			mxa=mxb=-1;
		}
	};
	struct Backup {
		int *var,val;
		Backup(){}Backup(int *var,int val):var(var),val(val){}
	}stack[MAXM];int top;
	void Assign(int &a,int b) {
		stack[++top]=Backup(&a,a);
		a=b;
	}
	void Fallback() {
		while(top) {
			*stack[top].var=stack[top].val;
			top--;
		}
	}
	struct DJU {
		int n;
		Node node[MAXN];
		typedef Node *Iter;
		void Reset() {
			for(int i=1;i<=n;++i)
				node[i].Reset();
		}
		int Root(int x) const {
			return !node[x].fa?x:Root(node[x].fa);	
		}
		Node *Get(int x) {
			return node+Root(x);
		}
		void Union(int x,int y,int a,int b,int type) {//临时操作必须在永久操作后面
			int pret=top,rx=Root(x),ry=Root(y);
			if(rx!=ry) {//return;//小的合到大的里面
				if(node[rx].sz<node[ry].sz) swap(rx,ry);
				Assign(node[ry].fa,rx);
				Assign(node[rx].sz,node[rx].sz+node[ry].sz);
			}
			Assign(node[rx].mxa,max(a,node[rx].mxa,node[ry].mxa));
			Assign(node[rx].mxb,max(b,node[rx].mxb,node[ry].mxb));
			top=type==PERM_OPT?pret:top;
		}
	};
}
using dju::DJU;
using dju::PERM_OPT;
using dju::TEMP_OPT;
using dju::Fallback;
DJU S;

struct Edges {
	int f,t,a,b,id;
}e[MAXM],q[MAXN],t[MAXN];
bool cmp_a(const Edges &e1,const Edges &e2) {
	return e1.a<e2.a;
}
bool cmp_b(const Edges &e1,const Edges &e2) {
	return e1.b<e2.b;
}
int main() {
//	freopen("input","r",stdin);	
	//注意：路径可以不是简单路径 :) :] :}
	static bool Ans[MAXN];
	int n,m;is>>n>>m;S.n=n;
	for(int i=1;i<=m;++i)
		is>>e[i].f>>e[i].t>>e[i].a>>e[i].b;
	int Q;is>>Q;
	for(int i=1;i<=Q;++i) {
		is>>q[i].f>>q[i].t>>q[i].a>>q[i].b;
		q[i].id=i;
	}	
	sort(e+1,e+1+m,cmp_a);
	int bsz=(int)sqrt(m+0.5);
	e[m+1].a=INT_MAX;
	for(int l=1,r=bsz;l<=m;l+=bsz,r=min(l+bsz-1,m)) {//每次循环 处理完所有a\in [p,p+bsz) 的询问
		int tc=0;
		for(int i=1;i<=Q;++i)
			if(q[i].a>=e[l].a && q[i].a<e[r+1].a)
				t[++tc]=q[i];
		sort(e+1,e+l,cmp_b);
		sort(t+1,t+1+tc,cmp_b);
		S.Reset();
		for(int i=1,pe=1;i<=tc;++i) {
			while(pe<=l && e[pe].b<=t[i].b) {
				S.Union(e[pe].f,e[pe].t,e[pe].a,e[pe].b,PERM_OPT);
				pe++;
			}
			for(int j=l;j<=r;++j)
				if(e[j].a<=t[i].a && e[j].b<=t[i].b)
					S.Union(e[j].f,e[j].t,e[j].a,e[j].b,TEMP_OPT);
			DJU::Iter pf=S.Get(t[i].f),pt=S.Get(t[i].t);
			Ans[t[i].id]=pf==pt && pf->mxa==t[i].a && pt->mxb==t[i].b;
			Fallback();
		}
	}
	for(int i=1;i<=Q;++i)
		os<<(Ans[i]?"Yes":"No")<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

如果没有S[a:b]S[a:b]中bb端点的限制，那就是直接把prefix[a∼b]prefix[a\sim b]和prefix[c]prefix[c]的 取最值再和d−c+1d-c+1。取min\min。这样的话，需要在rank[]rank[]上，查询rank[c]rank[c]在区间[a,b][a,b]中的前驱和后继。可以树套树或者可持久化 加了bb的限制，那就是一部分 会被截掉一段，可能本来是最长的，截掉之后就不是答案了。 然后通过某些神奇思考得到了二分的办法：对于答案midmid，只会出现在[a,b−mid+1][a,b-mid+1]。这样的话加一个二分答案，就巧妙地避免了限制的干扰，可以直接求rank[c]rank[c]的前驱后继再 $height[]$了。 另外，主席树的前驱后继似乎不好像平衡树那样直接走一遍，因为在上面不知道下面的某些点是否存在。

Tips

写出了形式化的条件，但没有想到二分答案的处理策略 应该是想一下去掉限制的想出主席树，再加上限制更容易得到二分答案.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "lucida"
#include "lucida"
using std::min;
using std::max;
using std::partial_sum;
using std::swap;
using std::fill;
const int MAXN=100000+11,LOG=20,INF=0x1f1f1f1f;
int log_2[MAXN];
struct _{_() {
	log_2[0]=-1;
	for(int i=1;i<MAXN;++i)
		log_2[i]=log_2[i>>1]+1;
}}Auto;
//写出了形式化的条件，但没有想到二分答案的处理策略
//应该是想一下去掉限制的想出主席树，再加上限制更容易得到二分答案.
namespace segTree {//兹瓷在区间中查询数的前驱后继
	const int SIZE=20*MAXN;
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node(int cnt):cnt(cnt) {
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE);
			return Me++;
		}
		void Up() {
			cnt=son[0]->cnt+son[1]->cnt;
		}
	}*_null=null=new Node(0),*_null_son=null->son[0]=null->son[1]=null;
	const int MODE_PRED=1,MODE_SUCC=0;
	struct SegTree {
		Node **root;int n,L,R;
		void Edit(Node *&pos,int L,int R,const int goal) {
			pos=new Node(*pos);//new Node(0)??
			if(L==R) pos->cnt++;
			else {
				int Mid=(L+R)>>1;
				if(goal<=Mid) Edit(pos->son[0],L,Mid,goal);
				else Edit(pos->son[1],Mid+1,R,goal);
				pos->Up();
			}
		}
		int Lowc(Node *pl,Node *pr,int L,int R,const int num) {
			if(L==R) return L<=num && pr->cnt-pl->cnt;// && [...
			else {
				int Mid=(L+R)>>1;
				if(num<=Mid) return Lowc(pl->son[0],pr->son[0],L,Mid,num);
				else return pr->son[0]->cnt-pl->son[0]->cnt+Lowc(pl->son[1],pr->son[1],Mid+1,R,num);
			}
		}
		int Kiss(Node *pl,Node *pr,int L,int R,int K) {
			if(L==R)
				return L;
			else {
				int Mid=(L+R)>>1,sum=pr->son[0]->cnt-pl->son[0]->cnt;
				if(K<=sum) return Kiss(pl->son[0],pr->son[0],L,Mid,K);
				else return Kiss(pl->son[1],pr->son[1],Mid+1,R,K-sum);
			}
		}
		SegTree(){}SegTree(int n,int L,int R,int a[]):n(n),L(L),R(R) {
			root=alloc(Node*,n+1);root[0]=null;
			for(int i=1;i<=n;++i)
				Edit(root[i]=root[i-1],L,R,a[i]);
		}
		int Rank(int l,int r,int num) {
			return Lowc(root[l-1],root[r],L,R,num)+1;
		}
		int Kiss(int l,int r,int K) {
			return K<=r-l+1 && K>=1?Kiss(root[l-1],root[r],L,R,K):-1;
		}
	};
}using segTree::SegTree;
struct SA {
	int rnk[MAXN],sa[MAXN],height[MAXN],st[LOG][MAXN],n;
	SA(){}SA(char *s,int n,int m):n(n) {
		static int temp[2][MAXN],*x=temp[0],*y=temp[1],cnt[MAXN];
		fill(cnt+1,cnt+1+m,0);
		for(int i=1;i<=n;++i) cnt[x[i]=s[i]]++;
		partial_sum(cnt+1,cnt+1+m,cnt+1);
		for(int i=n;i;--i) sa[cnt[x[i]]--]=i;
		for(int len=1;len<n;len<<=1) {
			int p=0;
			for(int i=n-len+1;i<=n;++i) y[++p]=i;
			for(int i=1;i<=n;++i) if(sa[i]-len>0) y[++p]=sa[i]-len;
			fill(cnt+1,cnt+1+m,0);
			for(int i=1;i<=n;++i) cnt[x[y[i]]]++;
			partial_sum(cnt+1,cnt+1+m,cnt+1);
			for(int i=n;i;--i) sa[cnt[x[y[i]]]--]=y[i];
			swap(x,y);p=0;
			for(int i=1;i<=n;++i)
				x[sa[i]]=y[sa[i-1]]==y[sa[i]] && (sa[i-1]+len<=n?y[sa[i-1]+len]:0)==(sa[i]+len<=n?y[sa[i]+len]:0)?p:++p;
			if((m=p)==n) break;
		}
		for(int i=1;i<=n;++i) rnk[sa[i]]=i;
		for(int i=1,len=0;i<=n;++i)
			if(rnk[i]!=1) {
				int j=sa[rnk[i]-1];
				while(s[i+len]==s[j+len]) len++;
				height[rnk[i]]=len;
				len-=(bool)len;
			}
		for(int i=1;i<=n;++i)
			st[0][i]=height[i];
		for(int lg=1;lg<=log_2[n];++lg)
			for(int i=1;i<=n-(1<<lg)+1;++i)
				st[lg][i]=min(st[lg-1][i],st[lg-1][i+(1<<(lg-1))]);
#ifdef debug
		for(int i=1;i<=n;++i)
			os<<i<<' '<<sa[i]<<' '<<height[i]<<' '<<(s+sa[i])<<'\n';
#endif
	}
	int operator () (int p1,int p2) {
		if(p1==p2) return n-p1+1;
		if((p1=rnk[p1])>(p2=rnk[p2])) swap(p1,p2);
		++p1;int lg=log_2[p2-p1+1];
		return min(st[lg][p1],st[lg][p2-(1<<lg)+1]);
	}
}sa;
SegTree seg;int n;
bool Check(int len,int a,int b,int c) {
	int l=a,r=b-len+1,rnk=seg.Rank(l,r,sa.rnk[c]),
		p1=seg.Kiss(l,r,rnk-1),
		p2=seg.Kiss(l,r,rnk);//查到了不存在的东西。没有测合法
	return max(~p1?sa(sa.sa[p1],c):0,~p2?sa(sa.sa[p2],c):0)>=len;
}
int Solve(int a,int b,int c,int d) {
	int L=0,R=min(d-c+1,b-a+1);
	while(L!=R) {
		int Mid=(L+R+1)>>1;
		if(Check(Mid,a,b,c)) L=Mid;
		else R=Mid-1;
	}
	return L;
}
int main() {
	freopen("input","r",stdin);
	static char s[MAXN];
	int m;is>>n>>m;
	is>>(s+1);new(&sa) SA(s,n,255);
	new(&seg) SegTree(n,1,n,sa.rnk);
	for(int i=1;i<=m;++i) {
		int a,b,c,d;is>>a>>b>>c>>d;
		int Ans=Solve(a,b,c,d);
		os<<Ans<<'\n';
	}
	return 0;
}
//11:28 finished

发表于 | 更新于

Link

Solution

反对称串长度一定为偶数 反对称串反掉一半之后一定是回文串 于是就试着求一下每个点左边的串反转之后，这个点的回文半径 回文串？于是考虑Manacher Manacher的主要条件是 A回文，B回文，那么C回文 现在考虑一下能不能直接套 A[1:A.length()2]RA[A.length()+12:A.length()]A[1:\dfrac {A.length()}2]^RA[\dfrac {A.length()+1}2:A.length()]回文 B[1:B.length()2]RB[B.length()+12:B.length()]B[1:\dfrac {B.length()}2]^RB[\dfrac {B.length()+1}2:B.length()]回文 是可以得到右边的CC回文的 所以直接套Manacher即可，每次把真字符取反；在分隔符处更新maxRight，统计答案。 至于为什么在分隔符处更新maxRight我也不知道，，只是如果每次都更新确实会多算一些不合法的

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include "lucida"
using std::min;
const int MAXN=500000+11;
int64 Manacher(int s[],int n) {
	static int ms[MAXN<<1]={-2},rad[MAXN<<1];
	for(int i=1;i<=n;++i) {
		ms[(i<<1)-1]=-1;
		ms[i<<1]=s[i];
	}
	ms[++(n<<=1)]=-1;ms[n+1]=-3;s=ms;
	int mxr=0,mxp=0;int64 res=0;
	for(int i=1;i<=n;++i) {
		rad[i]=i<=mxr+mxp-1?min(mxp+mxr-i,rad[2*mxp-i]):1;
		while(s[i-rad[i]]==s[i+rad[i]]) 
			rad[i]++;
		if(i+rad[i]>mxp+mxr && s[i]<0) {
			mxp=i;
			mxr=rad[i];
		}
		s[i]^=s[i]>=0;
		res+=((rad[i]-1)>>1)*(s[i]<0);
	}
	return res;
}
int main() {
	freopen("input","r",stdin);
	static int s[MAXN];
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		char ch;is>>ch;
		s[i]=ch-'0';
	}
	int64 Ans=Manacher(s,n);
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

先 O(n2)O(n^2)的枚举策略是从一个#开始向两边扩展，在扩展过程中如果两个指针位置的回文串都足够长，就更新答案，直到l,rl,r的距离超过了以ii为中心的回文半径。足够长，指l+rad[l]−1≥i≥r−rad[r]+1l+rad[l]-1\ge i \ge r-rad[r]+1 做了什么无用功呢？如果从左往右找，只要找到第一个l+rad[l]−1≥il+rad[l]-1\ge i的点，那就一定找到了以ii为中心的最长双倍回文，因为右指针的回文串与左指针的在距离不超过ii的回文半径的时候指向的字符串是对称的。 那么现在要解决的就是如何快速找到最靠左的ll使得l≥i−rad[i]2,l+rad[l]−1≥il\ge i-\dfrac {rad[i]}2,l+rad[l]-1\ge i 然后这个是有单调性的：l+rad[l]−1<i⇒l+rad[l]−1<i+1l+rad[l]-1< i\Rightarrow l+rad[l]-1< i+1 所以就可以考虑用一个维护单调递增的数据结构来优化 应该可以用单调队列？似乎不能，因为rad[]rad[]并不单调 但是orz Stilwell 很神奇地用了并查集 复杂度O(nlogn)O(n\log n)?

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include "lucida"
#include "lucida"
using std::min;
using std::copy;
const int MAXN=500000+11;
void Manacher(char *s,int &n,int rad[]) {
	static char ms[MAXN<<1]={'$'};
	for(int i=1;i<=n;++i) {
		ms[(i<<1)-1]='#';
		ms[i<<1]=s[i];
	}
	ms[++(n<<=1)]='#';
	ms[n+1]='@';copy(ms,ms+1+1+n,s);
	int mxp=0,mxr=0;
	for(int i=1;i<=n;++i) {
		rad[i]=i<=mxp+mxr-1?min(rad[2*mxp-i],mxp+mxr-i):1;
		while(s[i-rad[i]]==s[i+rad[i]]) 
			rad[i]++;
		if(i+rad[i]>mxp+mxr) {
			mxp=i;
			mxr=rad[i];
		}
	}
}
int fa[MAXN<<1];
int Root(int x) {
	return !fa[x]?x:fa[x]=Root(fa[x]);
}
int main() {
	freopen("input","r",stdin);
	static char s[MAXN<<1];
	static int rad[MAXN<<1];
	int n;is>>n>>(s+1);
	Manacher(s,n,rad);
	/*//x+rad[x]<=i+1<=x+rad[2*i-x]
	//找一个x最小的*/
	for(int i=2;i<=n;i+=2)
		fa[i]=i+1;//必须找偶数长度的
	int Ans=0;
	for(int i=1;i<=n;i+=2) {
		for(int j=Root(i-(rad[i]>>1));j<i;j=fa[j]=Root(j+1))
			if(j+rad[j]-1>=i) {
				chkmx(Ans,(i-j)*2);
				break;
			}
	}
	os<<Ans<<'\n';
	return 0;
}
/*
 4ms WA..没*2??
 */

发表于 | 更新于

Link

发现自己对容斥的理解还处于小学的水平，补点题找找感觉

Solution

首先这是求交集，被我当成并集想了大半天2333 求交集的话，那肯定是选kk个当交集，选出所有的集合剩下部分的交集为∅\emptyset 设f(n,i)f(n,i)表示从nn个元素的集合中选出交集至少有ii个元素的子集的方案数，考虑容斥 那么最后的答案就是 Cnk(∑i=0n−k(−1)if(n−k,i))C_n^k(\sum\limits_{i=0}^{n-k}(-1)^{i}f(n-k,i)) 应该是比较好懂的。。 又显然f(n,k)=Cn−ki(22n−k−1)f(n,k)=C_{n-k}^i(2^{2^{n-k}}-1)，−1-1是因为必须选至少一个

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include "lucida"

const int P=1000000007,MAXN=1000000+11;
int64 fac[MAXN],ifac[MAXN];
struct _{_(){
	ifac[1]=1;
	for(int i=2;i<MAXN;++i)
		ifac[i]=(P-P/i)*ifac[P%i]%P;
	fac[0]=ifac[0]=1;
	for(int i=1;i<MAXN;++i) {
		fac[i]=fac[i-1]*i%P;
		(ifac[i]*=ifac[i-1])%=P;	
	}
}}Prep;
int64 C(int n,int m) {
	return n>=m?fac[n]*ifac[m]%P*ifac[n-m]%P:0;
}
int64 Null(int n) {
	int64 res=0,p2p=2;
	for(int i=n;~i;--i,(p2p*=p2p)%=P)//n-1开始枚举的
		(res+=C(n,i)*(i&1?-1:1)*(p2p-1)%P)%=P;//外层没%
	return res;
}
int main() {
	freopen("input","r",stdin);
	int n,K;is>>n>>K;
	int64 Ans=Null(n-K)*C(n,K)%P;
	(Ans+=P)%=P;
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

Link

感觉这个“动态树”的脑洞开的挺不错的，，至少比“矩阵乘法(给你一个矩阵，不用做矩阵乘法，但需要询问矩阵内第K小的值)”好多了2333

Solution

求树链的交集的做法应该还是挺有意思的。。 虽然这个题用容斥只是为了容斥而容斥，，可以直接用线段树计算被标记的节点的和 但是为了写一下树链的交，写了容斥的写法

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include "lucida"
#include "lucida"
using std::swap;
const int MAXN=200000+11,MAXLOG=21;
namespace segtree {
	const int SIZE=MAXN<<1;
	struct Node {
		Node *son[2];
		int sumv,add;
		const int sz;
		Node(int val,int sz):sumv(val),add(0),sz(sz) {
			son[0]=son[1]=0;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,MAXN<<2);
			return Me++;
		}
		void Add(int d) {
			add+=d;
			sumv+=d*sz;
		}
		void Down() {
			if(add) {
				son[0]->Add(add);
				son[1]->Add(add);
				add=0;
			}
		}
		void Up() {
			sumv=son[0]->sumv+son[1]->sumv;
		}
	};
	struct SegTree {
		Node *root;
		int L,R;
		void Build(Node *&pos,int L,int R) {
			pos=new Node(0,R-L+1);
			if(L!=R) {
				int Mid=(L+R)>>1;
				Build(pos->son[0],L,Mid);
				Build(pos->son[1],Mid+1,R);
			}
		}
		int Access(Node *pos,int L,int R,int l,int r) {
			if(L==l && R==r)
				return pos->sumv;
			else {
				pos->Down();
				int Mid=(L+R)>>1;
				if(r<=Mid)
					return Access(pos->son[0],L,Mid,l,r);
				else if(Mid+1<=l)
					return Access(pos->son[1],Mid+1,R,l,r);
				else
					return Access(pos->son[0],L,Mid,l,Mid)
						  +Access(pos->son[1],Mid+1,R,Mid+1,r);
			}
		}
		void Edit(Node *pos,int L,int R,int l,int r,int d) {
			if(L==l && R==r)
				pos->Add(d);
			else {
				pos->Down();
				int Mid=(L+R)>>1;
				if(r<=Mid)
					Edit(pos->son[0],L,Mid,l,r,d);
				else if(Mid+1<=l)
					Edit(pos->son[1],Mid+1,R,l,r,d);
				else
					Edit(pos->son[0],L,Mid,l,Mid,d),
					Edit(pos->son[1],Mid+1,R,Mid+1,r,d);
				pos->Up();
			}
		}
		SegTree() {}
		SegTree(int L,int R):L(L),R(R) {
			Build(root,L,R);
		}
		int Query(int l,int r) {
			return Access(root,L,R,l,r);
		}
		void Edit(int l,int r,int d) {
			Edit(root,L,R,l,r,d);
		}
	};
}using segtree::SegTree;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
int dep[MAXN],fa[MAXN],sz[MAXN],prefer[MAXN],cht[MAXN],lbd[MAXN],rbd[MAXN],dfs[MAXN],dc,stlbd[MAXN],strbd[MAXN],stdfs[MAXN<<1],stdc;
void DFS(int pos) {
	dep[pos]=dep[fa[pos]]+1;
	sz[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre)
		if(e->to!=fa[pos]) {
			int u=e->to;
			fa[u]=pos;
			DFS(u);
			sz[pos]+=sz[u];
			prefer[pos]=sz[u]>sz[prefer[pos]]?u:prefer[pos];
		}
}
void Assign(int pos,int top) {
	dfs[++dc]=pos;
	lbd[pos]=dc;
	stdfs[++stdc]=pos;
	stlbd[pos]=stdc;
	cht[pos]=top;
	if(prefer[pos]) {
		Assign(prefer[pos],top);stdfs[++stdc]=pos;
		for(Edge *e=G[pos];e;e=e->pre)
			if(e->to!=fa[pos] && e->to!=prefer[pos]) {
				Assign(e->to,e->to);
				stdfs[++stdc]=pos;
			}
	}
	rbd[pos]=dc;
	strbd[pos]=stdc;
}
int log_2[MAXN<<1],st[MAXLOG][MAXN<<1];
void ST() {
	log_2[0]=-1;
	for(int i=1;i<=stdc;++i) {
		st[0][i]=stdfs[i];
		log_2[i]=log_2[i>>1]+1;
	}
	for(int lg=1,pl,pr;lg<=log_2[stdc];++lg)//log_2[dc]
		for(int i=1;i<=stdc-(1<<lg)+1;++i)//stdc.
			st[lg][i]=dep[pl=st[lg-1][i]]<dep[pr=st[lg-1][i+(1<<(lg-1))]]?pl:pr;	
}
int LCA(int p1,int p2) {
	p1=stlbd[p1],p2=stlbd[p2];
	if(p1>p2) swap(p1,p2);
	int lg=log_2[p2-p1+1],pl=st[lg][p1],pr=st[lg][p2-(1<<lg)+1];
	return dep[pl]<dep[pr]?pl:pr;
}
SegTree seg;
void Divide() {
	DFS(1);
	Assign(1,1);
	ST();
	new(&seg) SegTree(1,dc);
}
void SubTree(int pos,int delta) {
	seg.Edit(lbd[pos],rbd[pos],delta);
}
struct RTR {
	int top,bot;
	RTR(){}
	RTR(int top,int bot):top(top),bot(bot){}
	bool empty() {
		return top==-1;
	}
	bool full() {
		return top==0;
	}
	friend RTR operator & (RTR a,RTR b) {
		if(a.empty() || b.full())
			return a;
		if(b.empty() || a.full())
			return b;
		if(dep[a.top]<dep[b.top])
			swap(a,b);
		//int lca=LCA(a.top,b.top);
		if(LCA(a.top,b.bot)!=a.top)
			return RTR(-1,-1);
		else
			return RTR(a.top,LCA(a.bot,b.bot));
	}
	RTR &operator &=(RTR b){
		return *this=*this & b;
	}
	int Sum() {
		if(empty())
			return 0;
		int bt=bot,tp=top,res=0;
		while(cht[bt]!=cht[tp]) {
			res+=seg.Query(lbd[cht[bt]],lbd[bt]);
			bt=fa[cht[bt]];
		}
		res+=seg.Query(lbd[tp],lbd[bt]);
		return res;
	}
};
int Calc(int S,int qc,RTR q[]) {
	int cnt=0;
	RTR uni(0,0);
	for(int i=1;i<=qc;++i)
		if(S>>(i-1)&1) {
			++cnt;
			uni&=q[i];
		}
	return (cnt&1?1:-1)*uni.Sum();
}
int Query(int qc,RTR q[]) {
	int res=0;
	/*for(int i=1;i<=qc;++i)
		res+=q[i].Sum();*/
	for(int S=(1<<qc)-1;S;--S)
		res+=Calc(S,qc,q);
	return res;
}
int main() {
	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n-1;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	Divide();
	int Q;is>>Q;
	RTR q[6];
	for(int i=1;i<=Q;++i) {
		int opt,u,delta,K,Ans; 
		is>>opt;
		switch(opt) {
			case 0:
				is>>u>>delta;
				SubTree(u,delta);
				break;
			case 1:
				is>>K;
				for(int i=1;i<=K;++i) {
					is>>q[i].top>>q[i].bot;
					if(dep[q[i].top]>dep[q[i].bot])
						swap(q[i].top,q[i].bot);
				}
				Ans=Query(K,q)&((1u<<31)-1);
				os<<Ans<<'\n';
				break;
		}
	}
	return 0;
}

发表于 | 更新于

Link

我只想说：是谁想出的这么＊＊的DP？！

Solution

  1. 决定一个区间能否被删去的是其能否在一系列变化之后被一个串完全匹配掉。
  2. 不管原串如何变化，一堆小串是不动的

由此可以得到一个思路：区间能否被删除取决于小串；而小串是固定的，可以表示出区间变化之后的形态。也就是说，小串可以表示出可以决定删除的DP状态。 那就从小串入手，设计状态f[l][r][i][d]f[l][r][i][d]表示区间[l,r][l,r]删到最后能否只剩下第ii个小串的前dd个字符。可以看出，任何一个合法的删除序列，对于区间嵌套起来的一组消除，一定可以用这个状态表示。转移的时候需要一个辅助状态c[l][r]c[l][r]，表示区间[l,r][l,r]能否被完全消除，然后就做就行了。

Tips

设计DP状态的时候要找决定答案的量，要找不变或者确定可知的量。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include "lucida"
const int MAXL=160,MAXS=35,MAXP=25;
int main() {
	freopen("input","r",stdin);
	static bool f[MAXL][MAXL][MAXS][MAXP],c[MAXL][MAXL];
	static char L[MAXL],S[MAXS][MAXP];
	static int len[MAXS],minv[MAXL];
	int sn;
	is>>(L+1)>>sn;
	int n=strlen(L+1);
	for(int i=1;i<=sn;++i) {
		is>>(S[i]+1);
		len[i]=strlen(S[i]+1);
	}	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=sn;++j)
			f[i][i-1][j][0]=1;
	//f[l][r][i][d] 区间[l,r]能否匹配到S[i]的前t位
	//c[l][r] 区间[l,r]能否删干净
	for(int range=1;range<=n;++range)
		for(int l=1,r=range;r<=n;++l,++r) 
			for(int i=1;i<=sn;++i) {
				for(int d=1;d<=len[i];++d) {
					f[l][r][i][d]=(f[l][r-1][i][d-1] && L[r]==S[i][d]);
					for(int p=l;p<=r-1;++p)
						f[l][r][i][d]|=(f[l][p][i][d] && c[p+1][r]);
				}
				c[l][r]|=f[l][r][i][len[i]];
			}
	for(int i=1;i<=n;++i) {
		minv[i]=minv[i-1]+1;
		for(int j=1;j<=i;++j)
			if(c[j][i])
				chkmn(minv[i],minv[j-1]);
	}
	os<<minv[n]<<'\n';
	return 0;
}