发表于 | 更新于

Link

似乎是白书某个角落的一道思考题？？

Solution

把区间离散化成2n个点

连边

S->1 <K,0>

2n->T <K,0>

i->i+1 <inf,0>

l[i]->r[i] <1,w[i]>

然后跑最大费用最大流。

因为一条增广路互不相交，所以可以尽情走，走出K条就完成了任务。

发表于 | 更新于

Link

Solution

默认每天都碎觉，每长度为KK的区间，可以把 天转化成歘饭。。

修改一个点ii，可以影响的区间的右端点的区间为[i,i+K−1][i,i+K-1]。

现在问题转化成有n−K+1n-K+1点和nn个区间，选择一个区间会产生相应获利，在每个点有[l,r][l,r]个区间覆盖着的前提下，获利尽量大。

建图 

1
2
3
4
S'->S <r,0>
S->1..k <1,0>
i->i+1 <r-l,0>
i->i+k <1,s[i]-e[i]>

对于i≥Ki\ge K,一个i->i+1的剖面，流量是r。把不改变的天数限制在[0,r-l]，那么改变的天数就满足了限制。

对于i<Ki<K，?

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
#include <cstdio>
#include <string>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int MAXN=1000+11;
template <class T> inline
bool chkmx(T &a,T const &b) {
	return a<b?a=b,1:0;
}
template <class T> inline
bool chkmn(T &a,T const &b) {
	return a>b?a=b,1:0;
}
namespace MCMF {
const int INF=0x1f1f1f1f;
const int64 INF64=0x1f1f1f1f1f1f1f1fll;
struct Edge {
	int to,v,cap,cost;Edge *pre,*rev;
	Edge(int to,int cap,int cost,Edge *pre):to(to),v(0),cap(cap),cost(cost),pre(pre),rev(0) {}
}*G[MAXN],*preE[MAXN];
int S,T,n;
int *Adde(int f,int t,int cap,int cost) {
	G[f]=new Edge(t,cap,cost,G[f]);
	G[t]=new Edge(f,0,-cost,G[t]);
	G[f]->rev=G[t];G[t]->rev=G[f];
	return &G[f]->v;
}
int Aug() {
	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;
}
int64 dist[MAXN];
bool Path() {
	static bool inq[MAXN];
	static int Q[MAXN],he,ta;
	for(int i=0;i<=n;++i) {
		dist[i]=-INF64;
		inq[i]=0;
	}
	//队列有n+1个位置
	dist[S]=0;
	Q[he=0]=S;inq[S]=1;ta=1;
#define succ(i) ((i)==n?0:(i)+1)
	while(he!=ta) {
		int pos=Q[he];he=succ(he);inq[pos]=0;//丢人..
		for(Edge *e=G[pos];e;e=e->pre) if(e->cap>e->v) {
			int u=e->to;
			if(chkmx(dist[u],dist[pos]+e->cost)) {
				preE[u]=e;
				if(!inq[u]) {
					inq[u]=1;
					Q[ta]=u;
					ta=succ(ta);
				}
			}
		}
	}
	return dist[T]!=-INF64;
}
int64 Run() {
	int64 cost=0;
	int flow=0;
	while(Path()) {
		int f=Aug();
		flow+=f;
		cost+=dist[T]*f;
		//os<<cost<<'\n';
	}
	return cost;
}
/*namespace MCMF*/}
int main() {
	static int js[MAXN],je[MAXN],w[MAXN];
	int n,K,mSleep,mEat;
	is>>n>>K>>mSleep>>mEat;
	for(int i=1;i<=n;is>>js[i++]);
	for(int i=1;i<=n;is>>je[i++]);
	int64 sumjs=0;
	for(int i=1;i<=n;++i) {
		sumjs+=js[i];
		w[i]=je[i]-js[i];
	}
	static int *flow[MAXN];
	int limL=mEat,limR=K-mSleep;
	int SS=MCMF::S=0;
	int T=MCMF::T=n+1;
	int S=n+2;
	MCMF::n=n+3;
	//--K;
	MCMF::Adde(SS,S,limR,0);
	for(int i=1;i<=K;++i) {
		MCMF::Adde(S,i,0x1f1f1f1f,0);
	}
	for(int i=1;i<=n;++i) {
		MCMF::Adde(i,i+1,limR-limL,0);
		flow[i]=MCMF::Adde(i,std::min(i+K,T),1,w[i]);
	}
	os<<sumjs+MCMF::Run()<<'\n';
	for(int i=1;i<=n;++i) {
		os<<(*flow[i]?'E':'S');
	}os<<'\n';
	return 0;
}

发表于 | 更新于

真⋅\cdot对计数一窍不通。

Link

同样的题，人家写20行就搞定，我写120行依然出问题。

Solution

分类。 可以分成(a+b+c)+3d(a+b+c)+3d或者(a+d)+(b+c)+2e(a+d)+(b+c)+2e

第一种情况，枚举cc，枚举dd，维护一个数组找a+b=d−ca+b=d-c的方案数

第二种情况，有a<b<c<d,a<b=c<d,a=b<c=d,a=b=c=da<b<c<d,a<b=c<d,a=b<c=d,a=b=c=d四种。要分别处理，并且添加一个限制(比如限定当前选择的是最大的)确保不重复。

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
#include <cstdio>
#include <string>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#include <map>
#include <cstring>
#include <algorithm>
#define int64 long long
const int MAXN=5000+11,MAXA=2e7+11;
int64 C[MAXN][5];
struct AtFirst {
	AtFirst() {
		C[0][0]=1;
		for(int i=1;i<MAXN;++i) {
			C[i][0]=1;
			for(int j=1;j<=std::min(4,i);++j) {
				C[i][j]=C[i-1][j-1]+C[i-1][j];
			}
		}
	}
}autoRun;
int main() {
	int n;is>>n;
	static int a[MAXN];
	static int64 single[MAXA],sum2[MAXA];
	for(int i=1;i<=n;++i) {
		is>>a[i];
		single[a[i]]++;
	}
	std::sort(a+1,a+1+n);
	n=std::unique(a+1,a+1+n)-a-1;
	int64 Ans=0;
	//(a+b+c)+d
	for(int i=1;i<=n;++i) {
		//a<b<c a<b=c a=b<c a=b=c 没法这么分类.
		for(int j=i+1;j<=n;++j) {
			Ans+=C[single[a[j]]][3]*sum2[a[j]-a[i]]*single[a[i]]//;//C[single[a[j]]][2]..
				+C[single[a[j]]][3]*(a[i]*2<a[j] && a[j]-a[i]*2<a[i]?single[a[j]-a[i]*2]:0)*C[single[a[i]]][2];
									//!!!!!!!!!!!!!!
		}
		if(a[i]%3==0) {
			Ans+=C[single[a[i]]][3]*C[single[a[i]/3]][3];
		}
		for(int j=1;j<=i-1;++j) {
			sum2[a[i]+a[j]]+=single[a[i]]*single[a[j]];
		}
		sum2[a[i]<<1]+=C[single[a[i]]][2];
	}
	memset(sum2,0,sizeof(sum2));
	//(a+d)+(b+c)+2e
	for(int i=1;i<=n;++i) {
		//1 2 2 3 4 4 !!!!!!!
		for(int j=i+1;j<=n;++j) if(a[j]-a[i]<a[i]) {//>..
			Ans+=C[single[a[j]]][2]*single[a[j]-a[i]]*single[a[i]]*(sum2[a[j]]+((a[j]&1)==0?C[single[a[j]>>1]][2]:0))
				+C[single[a[j]]][2]*C[single[a[j]-a[i]]][2]*C[single[a[i]]][2];
		}
		//a=b<c=d
		//sum2全都是instinct的
		//a==b==c==d
		Ans+=C[single[a[i]]][4]*C[single[a[i]<<1]][2];
		for(int j=1;j<=i-1;++j) {
			sum2[a[i]+a[j]]+=single[a[i]]*single[a[j]];
		}
	}
	os<<Ans<<'\n';
	return 0;
}

发表于 | 更新于

被faebdc的shadow坑惨了。在考场上才发现自己的3D计算几何知识基本为0。

旋转

已知点P=(x,y,z)P=(x,y,z)，把它沿着 转动θ∘\theta^{\circ}（从与向量相对的角度看过去，点是逆时针旋转的） 首先可以给出绕三个轴的旋转矩阵

Rx(θ)=[1000cosθ−sinθ0sinθcosθ]R_x(\theta)=\begin{bmatrix} 1&0&0\\ 0&\cos\theta&-\sin\theta\\ 0&\sin\theta&\cos\theta \end{bmatrix}Ry(θ)=[cosθ0sinθ010−sinθ0cosθ]R_y(\theta)=\begin{bmatrix} \cos\theta&0&\sin\theta\\ 0&1&0\\ -\sin\theta&0&\cos\theta \end{bmatrix}

RyR_y有些不同，因为RyR_y的变化中zz等价成了二维的xx轴，xx被等价成了yy轴

Rz(θ)=[cosθ−sinθ0sinθcosθ0001]R_z(\theta)=\begin{bmatrix} \cos\theta&-\sin\theta&0\\ \sin\theta&\cos\theta&0\\ 0&0&1 \end{bmatrix}

对于这三个特殊的旋转轴我们已经有了解决方案了，那么对于任意的轴 要怎么办呢？我们可以将这个旋转分解： 将整个坐标轴旋转，使得旋转轴 和zz轴重合 再将点PP绕zz轴旋转θ\theta角 再将整个坐标轴旋转回原位

算了直接上结论。。Miskcoo

[cosθ+x2(1−cosθ)xy(1−cosθ)−zsinθxz(1−cosθ)+ysinθyx(1−cosθ)+zsinθcosθ+y2(1−cosθ)yz(1−cosθ)−xsinθzx(1−cosθ)−ysinθzy(1−cosθ)+xsinθcosθ+z2(1−cosθ)]\begin{bmatrix} \cos \theta + x^2(1 - \cos \theta) & xy(1 - \cos \theta) - z\sin \theta & xz(1 - \cos \theta) + y\sin \theta \\ yx(1 - \cos \theta) + z\sin \theta & \cos \theta + y^2(1 - \cos \theta) & yz(1 - \cos \theta) - x\sin \theta \\ zx(1 - \cos \theta) - y\sin \theta & zy(1 - \cos \theta) + x\sin \theta & \cos \theta + z^2(1 - \cos \theta) \end{bmatrix}

还是很优美的。

线面相交

设平面的法向量为 ，平面上有一点PP。有直线 。

设交点为CC，则

解得

当 的时候，显然交点不存在。

这种法线的操作对于二维的线线相交依然适用，比面积法或者体积法显然得多，好记得多，而且数值稳定性并没有损失。

一道题

附上一道练手题目：Shadow

这道题目存在更简洁的做法，但是为了强行套模板，我选择了一种非常难受的转化：把坐标系强行转化成地面是坐标平面，转化成把(0,0,0),B,C(0,0,0),B,C构成的三角形转到xOyxOy面上。详见代码，实在是恶心得不想多说。

写完1A好评。

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
#include <cstdio>
struct Istream {
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
	Istream &operator >>(double &x) {
		scanf("%lf",&x);
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(double const &x) {
		printf("%.2lf",x);
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#include <cmath>
#include <cassert>
#include <algorithm>
const int MAXN=100+11;
const double eps=1e-7,pi=acos(-1);
inline int sgn(double const &x) { return (x>eps)-(x<-eps); }
#define SELF_OPER(Type,op) template <class T> Type &operator op##=(T const &x) { return *this=*this op x; } 
namespace _3D {
typedef struct Point Vector;
struct Point {
	double x,y,z;
	Point() {}
	Point(double const &x,double const &y,double const &z):x(x),y(y),z(z) {}
	double Length() const { return sqrt(x*x+y*y+z*z); }
	friend double Inner(Vector const &a,Vector const &b) { return a.x*b.x+a.y*b.y+a.z*b.z; }
	friend Vector Outer(Vector const &a,Vector const &b) { return Vector(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x); }
	friend Point operator +(Point const &lhs,Vector const &rhs) { return Point(lhs.x+rhs.x,lhs.y+rhs.y,lhs.z+rhs.z); }
	friend Vector operator -(Point const &lhs,Point const &rhs) { return Vector(lhs.x-rhs.x,lhs.y-rhs.y,lhs.z-rhs.z); }
	friend Vector operator *(Vector const &lhs,double const &rhs) {	return Vector(lhs.x*rhs,lhs.y*rhs,lhs.z*rhs); }
	friend Vector operator /(Vector const &lhs,double const &rhs) {	return Vector(lhs.x/rhs,lhs.y/rhs,lhs.z/rhs); }
	SELF_OPER(Point,+)
	SELF_OPER(Point,-)
	SELF_OPER(Point,*)
	SELF_OPER(Point,/)
	friend double Angle(Vector const &v1,Vector const &v2) { return asin(Outer(v1,v2).Length()/(v1.Length()*v2.Length())); }
	friend Istream &operator >>(Istream &is,Point &p) {
		is>>p.x>>p.y>>p.z;
		return is;
	}
	friend Ostream &operator <<(Ostream &os,Point const &p) {
		os<<'('<<p.x<<','<<p.y<<','<<p.z<<')';
		return os;
	}
}p[MAXN];
struct Line {
	Point p;
	Vector v;
	Line() {}
	Line(Point const &p,Vector const &v):p(p),v(v) {}
};
Point Rotate(Line const &ln,Point p,double const &rad) {
	static double co,si;
	static Vector a;
	si=sin(rad),co=cos(rad);
	a=ln.v/ln.v.Length();
	double T[][3]={{co+a.x*a.x*(1-co),a.x*a.y*(1-co)-a.z*si,a.x*a.z*(1-co)+a.y*si},
				  {a.y*a.x*(1-co)+a.z*si,co+a.y*a.y*(1-co),a.y*a.z*(1-co)-a.x*si},
				  {a.z*a.x*(1-co)-a.y*si,a.z*a.y*(1-co)+a.x*si,co+a.z*a.z*(1-co)}};
	p-=ln.p;
	p=Point(p.x*T[0][0]+p.y*T[1][0]+p.z*T[2][0],
			p.x*T[0][1]+p.y*T[1][1]+p.z*T[2][1],
			p.x*T[0][2]+p.y*T[1][2]+p.z*T[2][2]);
	return p+=ln.p;
}
struct Plane {
	Point p;Vector nv;
	Plane(Point const &p1,Point const &p2,Point const &p3):p(p1),nv(Outer(p2-p1,p3-p1)) {}
};
const Plane GROUND(Point(0,0,0),Point(1,0,0),Point(0,1,0));
Point Cross(Line ln,Plane pln) {
	double d1=-Inner(pln.nv,ln.p-pln.p),d2=Inner(pln.nv,ln.v);//d1/d2
	if(d2==0) {
		throw;
	} else {
		return ln.p+ln.v*(d1/d2);
	}
}
}
namespace _2D {
typedef struct Point Vector;
struct Point {
	double x,y;
	Point() {}
	Point(double const &x,double const &y):x(x),y(y) {}
	friend bool operator <(Point const &lhs,Point const &rhs) {	return lhs.x==rhs.x?lhs.y<rhs.y:lhs.x<rhs.x; }
	friend Vector operator +(Point const &lhs,Vector const &rhs) { return Vector(lhs.x+rhs.x,lhs.y+rhs.y); }
	friend Vector operator -(Point const &lhs,Point const &rhs) { return Vector(lhs.x-rhs.x,lhs.y-rhs.y); }
	friend Vector operator *(Vector const &lhs,double const &rhs) { return Vector(lhs.x*rhs,lhs.y*rhs); }
	friend Vector operator /(Vector const &lhs,double const &rhs) {	return Vector(lhs.x/rhs,lhs.y/rhs); }
	friend double Inner(Vector const &a,Vector const &b) { return a.x*b.x+a.y*b.y; }
	friend double Outer(Vector const &a,Vector const &b) { return a.x*b.y-a.y*b.x; }
}p[MAXN];
struct Line {
	Point p;Vector v;
	Line() {}
	Line(Point const &p,Vector const &v):p(p),v(v) {}
};
Point Cross(Line const &ln1,Line const &ln2) {
	Vector norm(-ln2.v.y,ln2.v.x);
	double d1=-Inner(norm,ln1.p-ln2.p),d2=Inner(ln1.v,norm);
	return ln1.p+ln1.v*(d1/d2);
}
double HullSize(Point p[],int n) {
	std::sort(p+1,p+1+n);
	static Point stack[MAXN];
	int top=0;
	for(int i=1;i<=n;++i) {
		while(top>=2 && Outer(stack[top]-stack[top-1],p[i]-stack[top])<=0) {
			top--;
		}
		stack[++top]=p[i];
	}
	int mid=top;
	for(int i=n;i>=1;--i) {
		while(top>=mid+1 && Outer(stack[top]-stack[top-1],p[i]-stack[top])<=0) {
			top--;
		}
		stack[++top]=p[i];
	}
	if(top) {
		top--;
	}
	double res=0;
	for(int i=1;i<=top;++i) {
		res+=Outer(stack[i],stack[i==top?1:i+1]);
	}
	return res/2;
}
}
using namespace _3D;
void Transform(Point g[],Point &light,Point p[],int n) {
	Point &o=g[0];
	for(int i=1;i<=n;++i) {
		p[i]-=o;
	}
	light-=o;
	g[2]-=o;
	g[1]-=o;
	g[0]-=o;
	Line axis;double angle;
	axis=Line(o,Vector(-g[1].y,g[1].x,0));
	angle=sgn(g[1].x)==0 && sgn(g[1].y)==0?pi/2:Angle(g[1],Vector(g[1].x,g[1].y,0));
	if(sgn(Rotate(axis,g[1],angle).z)!=0) {
		angle*=-1;
	}
	for(int i=1;i<=n;++i) {
		p[i]=Rotate(axis,p[i],angle);
	}
	light=Rotate(axis,light,angle);
	g[1]=Rotate(axis,g[1],angle);
	g[2]=Rotate(axis,g[2],angle);
	assert(sgn(g[1].z)==0);

	_2D::Point _crs=_2D::Cross(_2D::Line(_2D::Point(g[2].x,g[2].y),_2D::Vector(-g[1].y,g[1].x)),_2D::Line(_2D::Point(0,0),_2D::Point(g[1].x,g[1].y)));
	Point crs=Point(_crs.x,_crs.y,0);
	axis=Line(o,g[1]);
	angle=sgn(g[2].x-crs.x)==0 && sgn(g[2].y-crs.y)==0?pi/2:Angle(g[2]-crs,Point(g[2].x,g[2].y,0)-crs);
	if(sgn(Rotate(axis,g[2],angle).z)!=0) {
		angle*=-1;
	}
	for(int i=1;i<=n;++i) {
		p[i]=Rotate(axis,p[i],angle);
	}
	light=Rotate(axis,light,angle);
	g[2]=Rotate(axis,g[2],angle);
	assert(sgn(g[2].z)==0);
}

int main() {
#ifdef DEBUG
	freopen("input","r",stdin);
#else
	freopen("shadow.in","r",stdin);
	freopen("shadow.out","w",stdout);
#endif
	Point g[3];is>>g[0]>>g[1]>>g[2];
	Point light;is>>light;
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		is>>p[i];
	}
	Transform(g,light,p,n);
	Plane pln(g[0],g[1],g[2]);
	for(int i=1;i<=n;++i) {
		Point crs=Cross(Line(light,p[i]-light),pln);
		_2D::p[i]=_2D::Point(crs.x,crs.y);
	}
	os<<_2D::HullSize(_2D::p,n)<<'\n';
	return 0;
}

发表于 | 更新于

Link

Solution

显然可以暴力DP。对小范围打表找规律可以得结论。 然后套Wallis公式 (2n)!!(2n−1)!!∼πn\dfrac {(2n)!!}{(2n-1)!!}\sim \sqrt{\pi n} Ans≈πn2n+1Ans\approx\dfrac {\sqrt{\pi n}}{2n+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
#include "lucida"
const int N=1e7,MAXN=N+11;
const double pi=acos(-1);
double Ans[MAXN];
void Prep() {
	Ans[0]=1;
	for(int i=1;i<=N;++i) {
		Ans[i]=Ans[i-1]/(2*i+1)*2*i;
	}
}
double Calc(int64 n) {
	if(n<=N) {
		return Ans[n];
	} else {
		return sqrt(pi*n)/(2*n+1); 
	}
}
int main() {
//	freopen("input","r",stdin);
	os.precision(20);
	Prep();
	int T;is>>T;
	while(T--) {
		int64 n;is>>n;
		os<<Calc(n)<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution

在树上画一画，可以发现路径覆盖的充分必要条件。 二维条件，转化成寻找覆盖一个点的权值第KK大矩阵的问题。 用整体二分实现

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
#include "lucida"
import swap;
import sort;
import copy;
import fill;
const int MAXN=40000+11,MAXLOG=17;
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;
int Ans[MAXN];
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 Matrix {
	int x1,x2,y1,y2,c;
	Matrix() {}
	Matrix(int x1,int x2,int y1,int y2,int c):x1(x1),x2(x2),y1(y1),y2(y2),c(c) {}
	friend bool operator <(const Matrix &a,const Matrix &b) {
		return a.c<b.c;
	}
	void Adjust() {
		if(x1>y1) {
			swap(x1,y1);
			swap(x2,y2);
		}
		if(!(x2<y1)) {
			throw;
		}
	}
}mtx[MAXN<<1];int mc;
struct Query {
	int x,y,K,id;
	friend bool operator <(const Query &a,const Query &b) {
		return a.x<b.x;
	}
}q[MAXN];
//盘子是矩形 水果是点 对于每个点 需要知道覆盖它的权值第K大的矩形!
//合法的矩形 [x1,x2] & [y1,y2] = () ! 只要让[x1,x2]都小就可以了！！
int par[MAXN][MAXLOG],fa[MAXN],dfs[MAXN],lbd[MAXN],rbd[MAXN],dc,dep[MAXN]={0,1};
void DFS(int pos) {
	par[pos][0]=fa[pos];
	for(int lg=1;lg<=log_2[dep[pos]];++lg) {
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	}
	dfs[lbd[pos]=++dc]=pos;
	for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
		int u=e->to;
		fa[u]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
	}
	rbd[pos]=dc;
}
int Jump(int pos,int len) {
	for(int lg=log_2[len];~lg;--lg) if(len>>lg&1) {
		pos=par[pos][lg];
	}
	return pos;
}
int LCA(int p1,int p2) {
	if(dep[p1]<dep[p2]) {
		swap(p1,p2);
	}
	p1=Jump(p1,dep[p1]-dep[p2]);
	if(p1!=p2) {
		for(int lg=log_2[dep[p1]-1];~lg;--lg) if(par[p1][lg]!=par[p2][lg]) {  // -  1 ?
			p1=par[p1][lg];p2=par[p2][lg];
		}
		p1=fa[p1];
	}
	return p1;
}

void Deal(int x,int y,int c) {
	if(lbd[x]>lbd[y]) {
		swap(x,y);
	}
	int lca=LCA(x,y);
	if(x==lca) {
		int sec=Jump(y,dep[y]-dep[x]-1);
		if(1<=lbd[sec]-1) {
			mtx[++mc]=Matrix(1,lbd[sec]-1,lbd[y],rbd[y],c);
		}
		if(rbd[sec]+1<=dc) {
			mtx[++mc]=Matrix(rbd[sec]+1,dc,lbd[y],rbd[y],c);
		}
	} else {
		mtx[++mc]=Matrix(lbd[x],rbd[x],lbd[y],rbd[y],c);
	}
}
struct Bit {
	int n,us[MAXN],ut,a[MAXN];
	Bit() {}
	Bit(int n):n(n),ut(0) {
		fill(us+1,us+1+n,0);
	}
	void Reset() {
		++ut;
	}
	void Add(int pos,int v) {
		for(;pos<=n;pos+=pos & -pos) {
			(a[pos]=us[pos]==ut?a[pos]:(us[pos]=ut,0))+=v;
		}
	}
	void Add(int l,int r,int v) {
		Add(l,v);
		Add(r+1,-v);
	}
	int At(int pos) {
		int res=0;
		for(;pos;pos-=pos & -pos) {
			res+=(a[pos]=us[pos]==ut?a[pos]:(us[pos]=ut,0));
		}
		return res;
	}
};
struct Scan {
	int x,y1,y2;
	bool isLeft;
	Scan() {}
	Scan(int x,int y1,int y2,bool isLeft):x(x),y1(y1),y2(y2),isLeft(isLeft) {}
	friend bool operator <(const Scan &a,const Scan &b) {
		return a.x!=b.x?a.x<b.x:!a.isLeft;
	}
};
//这次不能再重写了！！
void DC(int ml,int mr,int ql,int qr) {//在矩阵[ml,mr]的区间里面，查找询问[ql,qr]的答案.
//需要知道[ql,qr]的每个点，被[ml,mr]的矩阵覆盖了多少次.扫描线?
	static Bit bit(dc);
	static Scan scan[MAXN<<2];
	static Query t[MAXN];
	if(ml==mr) {
		for(int i=ql;i<=qr;++i) {
			Ans[q[i].id]=mtx[ml].c;
		}
	} else {
		int sc=0,mmid=(ml+mr)>>1;
		for(int i=ml;i<=mmid;++i) {
			scan[++sc]=Scan(mtx[i].x1,mtx[i].y1,mtx[i].y2,1);
			scan[++sc]=Scan(mtx[i].x2+1,mtx[i].y1,mtx[i].y2,0);
		}
		sort(scan+1,scan+1+sc);
		sort(q+ql,q+qr+1);
		bit.Reset();
		int tl=ql,tr=qr;
		for(int i=ql,sp=1;i<=qr;++i) {
			while(sp<=sc && scan[sp].x<=q[i].x) {
				bit.Add(scan[sp].y1,scan[sp].y2,scan[sp].isLeft?1:-1);		
				sp++;
			}
			int sum=bit.At(q[i].y);
			if(q[i].K<=sum) {
				t[tl++]=q[i];
			} else {
				q[i].K-=sum;
				t[tr--]=q[i];
			}
		}
		copy(t+ql,t+qr+1,q+ql);
		DC(ml,mmid,ql,tl-1);
		DC(mmid+1,mr,tr+1,qr);
	}
}
int main() {
//	freopen("input","r",stdin);
	int n,disc,qc;
	is>>n>>disc>>qc;
	for(int i=1;i<=n-1;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	DFS(1);
	for(int i=1;i<=disc;++i) {
		int x,y,c;is>>x>>y>>c;
		Deal(x,y,c);
	}
	for(int i=1;i<=mc;++i) {
		mtx[i].Adjust();
	}
	sort(mtx+1,mtx+1+mc);
	for(int i=1;i<=qc;++i) {
		is>>q[i].x>>q[i].y>>q[i].K;
		q[i].id=i;
		if((q[i].x=lbd[q[i].x])>(q[i].y=lbd[q[i].y])) {
			swap(q[i].x,q[i].y);
		}
	}
	sort(q+1,q+1+qc);
	DC(1,mc,1,qc);
	for(int i=1;i<=qc;++i) {
		os<<Ans[i]<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution 树链剖分套主席树

先不管颜色的限制 形式化条件：(len[x]len[x]为xx到根节点的距离) Ans=∑poslen[u]+len[pos]−len[lca(pos,u)]Ans=\sum\limits_{pos} len[u]+len[pos]-len[lca(pos,u)] 可以把len[u]len[u]和len[pos]len[pos]都提出来，答案就变成了计算∑poslen[lca(pos,u)]\sum\limits_{pos}len[lca(pos,u)] 也就是u,posu,pos到根节点路径的交集。这个可以通过先把每个点到根节点的路径都覆盖一遍，查询时候只需要统计出∑v[e]coverCnt[e]\sum v[e]coverCnt[e]即可。可以通过线段树实现。其中标记永久化的处理非常有意思。 套上了颜色的限制，就仿照序列主席树的做法，把点按照颜色排序，顺序依次覆盖。 空间上界是O(nlog2n)O(n\log^2 n)的，但是似乎跑不满。 时间是O(nlog2n)O(n\log^2 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
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
#include "lucida"
using std::min;
using std::max;
using std::fill;
using std::sort;
using std::unique;
using std::lower_bound;
using std::upper_bound;
using std::partial_sum;
const int MAXN=150000+11,MAXLOGN=20;
int nums[MAXN],nc,a[MAXN],order[MAXN];
bool CompareValue(const int &i,const int &j) {
	return a[i]<a[j];
}
struct Edge {
	int to,v;Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t,int v) {
	G[f]=new Edge(t,v,G[f]);
	G[t]=new Edge(f,v,G[t]);
}
int64 pref[MAXN];
namespace segtree {
	const int SIZE=MAXN*MAXLOGN*7;
	struct Node *null;
	struct Node {
		Node *son[2];
		int64 sumv;int covc;
		Node():sumv(0) {
			son[0]=son[1]=null;
		}
		void *operator new(size_t) {
			static Node *Me=alloc(Node,SIZE),*Pool=Me;
			assert(Me-Pool<SIZE);
			return Me++;
		}
	}*_null=null=new Node,*_null_son=null->son[0]=null->son[1]=null;
	class SegTree {
	public:
		SegTree() {}
		SegTree(int n,int L,int R):root(alloc(Node*,n+1)),L(L),R(R) {
			fill(root,root+1+n,null);
		}
		void Add(int rc,int l,int r) {
			Edit(root[rc]=root[rc]==null?root[rc-1]:root[rc],L,R,l,r);
		}
		int64 Sum(int cl,int cr,int l,int r) {
			return Access(root[cl-1],root[cr],L,R,l,r);
		}
	private:
		Node **root;int L,R;
		void Edit(Node *&pos,int L,int R,int l,int r) {
			pos=new Node(*pos);
			if(L==l && R==r) {
				pos->covc++;
			} else {
				pos->sumv+=pref[r]-pref[l-1];
				int Mid=(L+R)>>1;
				if(r<=Mid) {
					Edit(pos->son[0],L,Mid,l,r);
				} else if(Mid+1<=l) {
					Edit(pos->son[1],Mid+1,R,l,r);
				} else {
					Edit(pos->son[0],L,Mid,l,Mid);
					Edit(pos->son[1],Mid+1,R,Mid+1,r);
				}
			}
		}
		int64 Access(Node *pl,Node *pr,int L,int R,int l,int r) {
			int64 res=(pref[r]-pref[l-1])*(pr->covc-pl->covc);
			if(L==l && R==r) {
				res+=pr->sumv-pl->sumv;//covc
			} else {
				int Mid=(L+R)>>1;
				if(r<=Mid) {
					res+=Access(pl->son[0],pr->son[0],L,Mid,l,r);
				} else if(Mid+1<=l) {
					res+=Access(pl->son[1],pr->son[1],Mid+1,R,l,r);
				} else {
					res+=Access(pl->son[0],pr->son[0],L,Mid,l,Mid)+Access(pl->son[1],pr->son[1],Mid+1,R,Mid+1,r);
				}
			}
			return res;
		}
	};
}using segtree::SegTree;
SegTree seg;
int fa[MAXN],dep[MAXN],sz[MAXN],prefer[MAXN],cht[MAXN],dfn[MAXN],dfs[MAXN],dc,total[MAXN];
int64 len[MAXN],cpfLen[MAXN];
void DFS(int pos) {
	sz[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
		int u=e->to;
		len[u]=len[pos]+e->v;
		fa[u]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
		sz[pos]+=sz[u];
		prefer[pos]=sz[u]>sz[prefer[pos]]?u:prefer[pos];
	}
}
void Assign(int pos) {
	dfs[dfn[pos]=++dc]=pos;
	if(prefer[pos]) {
		cht[prefer[pos]]=cht[pos];Assign(prefer[pos]);
		for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos] && e->to!=prefer[pos]) {
			int u=e->to;
			cht[u]=u;
			Assign(u);
		}
	}
}
void Divide() {
	dep[1]=1;DFS(1);
	cht[1]=1;Assign(1);
	new(&seg) SegTree(nc,1,dc);
	for(int i=1;i<=dc;++i) {
		pref[i]=pref[i-1]+len[dfs[i]]-len[fa[dfs[i]]];
		cpfLen[a[i]]+=len[i];
	}
	partial_sum(cpfLen+1,cpfLen+1+nc,cpfLen+1);
}
void Modify(int pos) {
	int color=a[pos];
	while(pos) {
		seg.Add(color,dfn[cht[pos]],dfn[pos]);//把路径上的边都覆盖一下
		pos=fa[cht[pos]];
	}
}
int64 Query(int pos,int cl,int cr) {
	int64 res=(int64)(total[cr]-total[cl-1])*len[pos]+cpfLen[cr]-cpfLen[cl-1];//total[]
	while(pos) {
		res-=seg.Sum(cl,cr,dfn[cht[pos]],dfn[pos])<<1;//统计路径上覆盖的边权和(可以重复)
		pos=fa[cht[pos]];
	}
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,Q,A;is>>n>>Q>>A;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		nums[i]=a[i];
	}
	sort(nums+1,nums+1+n);
	nc=unique(nums+1,nums+1+n)-nums-1;
	for(int i=1;i<=n;++i) {
		a[i]=lower_bound(nums+1,nums+1+nc,a[i])-nums;//+nc
		order[i]=i;
		total[a[i]]++;
	}
	partial_sum(total+1,total+1+n,total+1);
	sort(order+1,order+1+n,CompareValue);
	for(int i=1;i<=n-1;++i) {
		int a,b,c;is>>a>>b>>c;
		Adde(a,b,c);
	}
	Divide();
	for(int i=1;i<=n;++i) {
		Modify(order[i]);
	}
	int64 last=0;
	for(int i=1;i<=Q;++i) {
		int x;int64 a,b,l,r;is>>x>>a>>b;
		l=min((a+last)%A,(b+last)%A);
		r=max((a+last)%A,(b+last)%A);
		last=Query(x,lower_bound(nums+1,nums+1+nc,l)-nums,upper_bound(nums+1,nums+1+nc,r)-nums-1);
		os<<last<<'\n';
	}
	return 0;
}

Solution 点分治

这个做法比较显然，保留分治结构，用vector记录按照颜色排序之后的前缀和。查询时二分查找。 时间O(nlog2n)O(n\log^2n)，空间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
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
#include "lucida"
import max;
import sort;
import swap;
import pair;
import unique;
import upper_bound;
import lower_bound;
const int MAXN=150000+11,MAXLOG=20;
int nums[MAXN],nc,a[MAXN];
struct Edge {
	int to,v;Edge *pre;
	Edge(int to,int v,Edge *pre):to(to),v(v),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t,int v) {
	G[f]=new Edge(t,v,G[f]);
	G[t]=new Edge(f,v,G[t]);
}
namespace lca {
	int dep[MAXN],stdfs[MAXN<<1],stdc,stdfn[MAXN<<1],st[MAXLOG][MAXN<<1],log_2[MAXN<<1];int64 len[MAXN];
	void DFS(int pos) {
		stdfs[stdfn[pos]=++stdc]=pos;
		for(Edge *e=G[pos];e;e=e->pre) if(!stdfn[e->to]) {
			dep[e->to]=dep[pos]+1;
			len[e->to]=len[pos]+e->v;
			DFS(e->to);
			stdfs[++stdc]=pos;
		}
	}
	void Init() {
		DFS(1);
		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 pl,pr,lg=1;lg<=log_2[stdc];++lg) {
			for(int i=1;i<=stdc-(1<<lg)+1;++i) {
				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=stdfn[p1],p2=stdfn[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;
	}
	int64 Dist(int p1,int p2) {
		int lca=LCA(p1,p2);
		return len[p1]+len[p2]-2*len[lca];
	}
}using lca::Dist;	
namespace dc {
	//分治完了之后，保存分治结构
	//在每个重心，记录下方的点，按照颜色排序，并且计算到这个点的距离的前缀和 用vector 空间? n log n
	//查询?
	//从该点沿着分治结构向上走，记录路径长度，另一段乘上个数 加上去
	int sz[MAXN],tol;
	bool ud[MAXN];
	void GetSize(int pos,int from) {
		sz[pos]=1;
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to] && e->to!=from) {
			int u=e->to;
			GetSize(u,pos);
			sz[pos]+=sz[u];
		}
	}
	int DP(int pos,int from) {
		static int f[MAXN]={INT_MAX};
		int res=0,mxs=0;
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to] && e->to!=from) {
			int u=e->to;
			int temp=DP(u,pos);
			res=f[res]<f[temp]?res:temp;
			chkmx(mxs,sz[u]);
		}
		f[pos]=max(mxs,tol-sz[pos]);
		return f[pos]<f[res]?pos:res;
	}
	int Center(int rt) {
		GetSize(rt,0);
		tol=sz[rt];
		return DP(rt,0);
	}
	struct Node {
		int color;
		int64 sum;
		Node(int color,int64 sum):color(color),sum(sum) {}
		friend bool operator <(const Node &a,const Node &b) {
			return a.color<b.color;
		}
	};
	
	array<Node> path[MAXN],anti[MAXN];int uplayer[MAXN];
	void DFS(int pos,int from,int64 dist,array<Node> &arr) {
		arr.push_back(Node(a[pos],dist));
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to] && e->to!=from) {
			int u=e->to;
			DFS(u,pos,dist+e->v,arr);
		}
	}
	void DC(int pos) {
		ud[pos]=1;
		path[pos].push_back(Node(a[pos],0));//..
		for(Edge *e=G[pos];e;e=e->pre) if(!ud[e->to]) {
			int u=e->to,gcu=Center(u);
			DFS(u,pos,e->v,anti[gcu]);
			uplayer[gcu]=pos;
			path[pos].insert(path[pos].end(),anti[gcu].begin(),anti[gcu].end());
			sort(anti[gcu].begin(),anti[gcu].end());
			for(int i=1,ei=anti[gcu].size();i<ei;++i) {//i=1?????
				anti[gcu][i].sum+=anti[gcu][i-1].sum;
			}
			DC(gcu);
		}
		sort(path[pos].begin(),path[pos].end());
		for(int i=1,ei=path[pos].size();i<ei;++i) {
			path[pos][i].sum+=path[pos][i-1].sum;
		}
	}
	void Run() {
		DC(Center(1));
	}
	pair<int64,int> Calc(array<Node> &ar,int l,int r) {
		int pl=lower_bound(ar.begin(),ar.end(),Node(l,0))-ar.begin(),
			pr=upper_bound(ar.begin(),ar.end(),Node(r,0))-ar.begin()-1;
		return pl!=(int)ar.size() && ~pr?pair<int64,int>(ar[pr].sum-(pl?ar[pl-1].sum:0),pr-pl+1):pair<int64,int>(0,0);
	}
	int64 Query(int pos,int l,int r) {
		int64 res=Calc(path[pos],l,r).first;int s=pos;
		while(uplayer[pos]) {
			pair<int64,int> cur=Calc(path[uplayer[pos]],l,r),ant=Calc(anti[pos],l,r);
			res+=cur.first-ant.first+(cur.second-ant.second)*Dist(s,uplayer[pos]);
			pos=uplayer[pos];
		}
		return res;
	}
}using dc::Run;using dc::Query;
int main() {
//	freopen("input","r",stdin);
	int n,Q,A;is>>n>>Q>>A;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		nums[i]=a[i];
	}
	sort(nums+1,nums+1+n);
	nc=unique(nums+1,nums+1+n)-nums-1;
	for(int i=1;i<=n;++i) {
		a[i]=lower_bound(nums+1,nums+1+nc,a[i])-nums;
	}
	for(int i=1;i<=n-1;++i) {
		int a,b,c;is>>a>>b>>c;
		Adde(a,b,c);
	}
	lca::Init();
	dc::Run();
	int64 last=0;
	for(int i=1;i<=Q;++i) {
		int x;int64 a,b,l,r;is>>x>>a>>b;
		l=(a+last)%A;r=(b+last)%A;
		a=l<r?l:r;b=l<r?r:l;
		l=a;r=b;
		last=Query(x,lower_bound(nums+1,nums+1+nc,l)-nums,upper_bound(nums+1,nums+1+nc,r)-nums-1);
		os<<last<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution

想了一种可持久化可并堆的做法，感觉空间要炸 再仔细想想： 1≤K≤201\le K\le 20MDZZ!!

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
#include "lucida"
using std::swap;
const int MAXN=40000+11,MAXV=1000,MAXLOG=20;
int log_2[MAXN<<1];
struct _{_(){
	log_2[0]=-1;
	for(int i=1;i<(MAXN<<1);++i) {
		log_2[i]=log_2[i>>1]+1;
	}
}}Auto;
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 force[MAXN],place[MAXN];
namespace segtree {
	const int SIZE=MAXN*MAXLOG*MAXLOG;
	struct Node *null;
	struct Node {
		Node *son[2];
		int cnt;
		Node():cnt(0) {
			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,*_null_son=null->son[0]=null->son[1]=null;
	class SegTree {
	public:
		typedef Node *Iter;
		Node *root;
		SegTree() {}
		SegTree(int L,int R):root(null),L(L),R(R) {}
		void Add(int pos,int v) {
			Edit(root,L,R,pos,v);
		}
	private:
		int L,R;
		void Edit(Node *&pos,int L,int R,int goal,int v) {
			pos=pos==null?new Node:pos;
			if(L==R) {
				pos->cnt+=v;
			} else {
				int Mid=(L+R)>>1;
				goal<=Mid?Edit(pos->son[0],L,Mid,goal,v):Edit(pos->son[1],Mid+1,R,goal,v);
				pos->Up();
			}
		}
	};
}using segtree::SegTree;

int stdfs[MAXN<<1],stdc,stdfn[MAXN],st[MAXLOG][MAXN<<1],dep[MAXN],fa[MAXN],lbd[MAXN],rbd[MAXN],dfs[MAXN],dc;
void ST() {
	for(int i=1;i<=stdc;++i) {
		st[0][i]=stdfs[i];
	}
	for(int lg=1;lg<=log_2[stdc];++lg) {
		for(int i=1;i<=stdc-(1<<lg)+1;++i) {
			int pl=st[lg-1][i],pr=st[lg-1][i+(1<<(lg-1))];
			st[lg][i]=dep[pl]<dep[pr]?pl:pr;
		}
	}
}
int LCA(int p1,int p2) {
	p1=stdfn[p1],p2=stdfn[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;
}
void DFS(int pos) {
	stdfs[stdfn[pos]=++stdc]=pos;
	dfs[lbd[pos]=++dc]=pos;
	for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
		int u=e->to;
		fa[u]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
		stdfs[++stdc]=pos;
	}
	rbd[pos]=dc;
}

class Bit {
public:
	Bit() {}
	Bit(int n):seg(alloc(SegTree,n+1)),n(n) {
		for(int i=0;i<=n;++i) {
			new(&seg[i]) SegTree(1,MAXV);
		}
	}
	int Kiss(int p1,int p2,int K) {
		static SegTree::Iter plus[MAXN],minus[MAXN];
		int lca=LCA(p1,p2);
		int plc=FindNode(lbd[p1],plus);
		plc+=FindNode(lbd[p2],plus+plc);
		int mnc=FindNode(lbd[lca],minus);
		mnc+=FindNode(lbd[fa[lca]],minus+mnc);
		int tol=0;
		for(int i=1;i<=plc;++i) {
			tol+=plus[i]->cnt;
		}
		for(int i=1;i<=mnc;++i) {
			tol-=minus[i]->cnt;
		}
		if(tol<K) {
			return -1;
		}
		int L=1,R=MAXV;//1.
		while(L!=R) {
			int tol=0;
			for(int i=1;i<=plc;++i) {
				tol+=plus[i]->son[1]->cnt;
			}
			for(int i=1;i<=mnc;++i) {
				tol-=minus[i]->son[1]->cnt;
			}
			int dir=K<=tol;
			for(int i=1;i<=plc;++i) {
				plus[i]=plus[i]->son[dir];
			}
			for(int i=1;i<=mnc;++i) {
				minus[i]=minus[i]->son[dir];
			}
			int Mid=(L+R)>>1;
			if(K<=tol) {
				L=Mid+1;
			} else {
				R=Mid;
				K-=tol;
			}
		}
		return L;
	}
	void Add(int pos,int val,int d) {
		for(int i=pos;i<=n;i+=i & -i) {
			seg[i].Add(val,d);
		}
	}
private:
	SegTree *seg;int n;
	int FindNode(int pos,SegTree::Iter nodes[]) {
		int cnt=0;
		for(int i=pos;i;i-=i & -i) {
			nodes[++cnt]=seg[i].root;
		}
		return cnt;
	}
}bit;
void Init() {
	DFS(1);
	ST();
	new(&bit) Bit(dc);
}
void Modify(int x,int y) {
	bit.Add(lbd[place[x]],force[x],-1);
	bit.Add(rbd[place[x]]+1,force[x],1);
	bit.Add(lbd[place[x]],force[x]=y,1);
	bit.Add(rbd[place[x]]+1,force[x],-1);
}
void Move(int x,int to) {
	bit.Add(lbd[place[x]],force[x],-1);
	bit.Add(rbd[place[x]]+1,force[x],1);
	bit.Add(lbd[place[x]=to],force[x],1);
	bit.Add(rbd[place[x]]+1,force[x],-1);
}
int Query(int p1,int p2,int K,int Ans[]) {
	int cnt=0;
	for(int i=1;i<=K;++i) {
		if((Ans[++cnt]=bit.Kiss(p1,p2,i))==-1) {
			cnt--;
			break;
		}
	}
	return cnt;
}
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);
	}
	int m;is>>m;
	Init();
	for(int i=1;i<=m;++i) {
		is>>force[i]>>place[i];
		bit.Add(lbd[place[i]],force[i],1); 
		bit.Add(rbd[place[i]]+1,force[i],-1);
	}
	int Q,K;is>>Q>>K;
	static int Ans[30],ac;
	for(int i=1;i<=Q;++i) {
		int opt,x,y;is>>opt>>x>>y;
		switch(opt) {
			case 1:
				if(!(ac=Query(x,y,K,Ans))) {
					os<<-1<<'\n';
				} else {
					for(int i=1;i<=ac;++i) {
						os<<Ans[i]<<' ';//<<(i==ac?'\n':' ');
					}
					os<<'\n';
				}
				break;
			case 2:
				Move(x,y);
				break;
			case 3:
				Modify(x,y);
				break;
		}
	}
	return 0;
}

发表于 | 更新于

Link

Solution

非常神奇的思路。 每个集合BkB_k的元素一定是≤k\le k的数字。这些数字，是几个集合求交的得到的。一切集合追溯到本源，都来源于虚无(∅\emptyset)。如果把每个集合抽象成到∅\emptyset的路径，每个集合的构造过程就是几条路径的并集，加上一个新点。这是一个树结构，然后就可以通过LCA实现求交，通过DFS序实现求并集的大小。

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
#include "lucida"
import swap;
import sort;
const int MAXN=200000+11,MAXLOG=20;//儮儈儈儈儈儈
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;
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);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
}
int par[MAXN][MAXLOG],dep[MAXN];
void Link(int pos,int fa) {
	Adde(fa,pos);
	par[pos][0]=fa;
	dep[pos]=dep[fa]+1;
	for(int lg=1;lg<=log_2[dep[pos]];++lg) {
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	}
}
int LCA(int p1,int p2) {
	if (dep[p1]<dep[p2]) {
		swap(p1,p2);
	}
	for(int len=dep[p1]-dep[p2],lg=log_2[len];~lg;--lg) if(len>>lg&1) {
		p1=par[p1][lg];
	}
	if(p1!=p2) {
		for(int lg=log_2[dep[p1]];~lg;--lg) if(par[p1][lg]!=par[p2][lg]) {
			p1=par[p1][lg];
			p2=par[p2][lg];
		}
		p1=par[p1][0];
	}
	return p1;
}
int dfn[MAXN],dc;
void DFS(int pos) {
	dfn[pos]=++dc;
	for(Edge *e=G[pos];e;e=e->pre) {
		int u=e->to;
		DFS(u);
	}
}
bool cmpDFN(const int &p1,const int &p2) {
	return dfn[p1]<dfn[p2];
}
int main() {
//	freopen("input","r",stdin);
	//A_i 的元素都比i小
	//B_k 最大的元素一定是k 
	int n;is>>n;
	for(int i=1;i<=n;++i) {
		int lca=-1,cnt;is>>cnt;
		for(int j=1;j<=cnt;++j) {
			int x;is>>x;
			lca=lca==-1?x:LCA(x,lca);
		}
		Link(i,lca=lca==-1?0:lca);
	}
	DFS(0);
	int Q;is>>Q;
	for(int rep=1;rep<=Q;++rep) {
		int cnt;is>>cnt;
		static int x[MAXN];
		for(int i=1;i<=cnt;++i) {
			is>>x[i];
		}
		sort(x+1,x+1+cnt,cmpDFN);
		int Ans=0;
		for(int i=1;i<=cnt-1;++i) {
			Ans+=dep[x[i]]-dep[LCA(x[i],x[i+1])];
		}
		Ans+=dep[x[cnt]];
		os<<Ans<<'\n';
	}
	return 0;
}

发表于 | 更新于

Link

Solution

对[1..n][1..n]这个答案序列分块！！为什么我总是想把树分块。。。 想到这，接着就比较好说了。 修改一个点对块的影响，是使得它在块内的祖先的权值都相应变化。块内的祖先个数，可以O(nn)O(n\sqrt n)地预处理出来。 这样整块的统计是O(n)O(\sqrt n)的，那么零碎部分的也尽量O(n)O(\sqrt n)，那就要求每个点的求值是O(1)O(1)的。显然常见套路树状数组做不到。 那么再用dfs序分块替代树状数组。同样支持区间修改，询问变成O(1)O(1)，修改O(n)O(\sqrt n)。总复杂度就是O(nn)O(n\sqrt 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
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
#include "lucida"
import copy;
typedef unsigned long long qword;
const int MAXN=1e5+11,MAXB=320;
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 bsz,bs[MAXN],bt[MAXN],bc,bn[MAXN],parCnt[MAXN][MAXB];
qword bAns[MAXB],pref[MAXN];
int64 a[MAXN],mrk[MAXB];
int fa[MAXN],lbd[MAXN],rbd[MAXN],dfs[MAXN],dc;
qword DFS(int pos) {
	static int cnt[MAXB];//存储祖先 每块的个数
	qword sum=a[pos];
	cnt[bn[pos]]++;
	dfs[lbd[pos]=++dc]=pos;
	copy(cnt+1,cnt+1+bc,parCnt[pos]+1);
	for(Edge *e=G[pos];e;e=e->pre) if(e->to!=fa[pos]) {
		int u=e->to;
		fa[u]=pos;
		sum+=DFS(u);
	}
	cnt[bn[pos]]--;
	bAns[bn[pos]]+=sum;
	rbd[pos]=dc;
	return sum;
}
void Change(int pos,int64 v) {
	for(int b=1;b<=bc;++b) {
		bAns[b]+=(v-a[pos])*parCnt[pos][b];
	}
	int dfn=lbd[pos];
	for(int b=bn[dfn]+1;b<=bc;++b) {
		mrk[b]+=v-a[pos];
	}
	for(int i=dfn;i<=bt[bn[dfn]];++i) {
		pref[i]+=v-a[pos];
	}
	a[pos]=v;
}
qword SbtSum(int rt) {
	return (pref[rbd[rt]]+mrk[bn[rbd[rt]]])-(pref[lbd[rt]-1]+mrk[bn[lbd[rt]-1]]);
}
qword Query(int l,int r) {
	qword res=0;
	if(bn[l]==bn[r]) {
		for(int i=l;i<=r;++i) {
			res+=SbtSum(i);
		}
	} else {
		for(int b=bn[l]+1;b<=bn[r]-1;++b) {
			res+=bAns[b];
		}
		for(int i=l;i<=bt[bn[l]];++i) {
			res+=SbtSum(i);
		}
		for(int i=bs[bn[r]];i<=r;++i) {
			res+=SbtSum(i);
		}
	}
	return res;
}
int main() {
//	freopen("input","r",stdin);
	int n,m;is>>n>>m;
	bsz=sqrt(n+0.5);
	for(int i=1;i<=n;++i) {
		is>>a[i];
		bn[i]=(i-1)/bsz+1;
		if(bn[i]!=bn[i-1]) {
			bs[bn[i]]=i;
			bt[bn[i-1]]=i-1;
		}
	}
	bt[bc=bn[n]]=n;
	int root;
	for(int i=1;i<=n;++i) {
		int x,y;is>>x>>y;
		if(x) {
			Adde(x,y);
		} else {
			root=y;
		}
	}
	DFS(root);
	for(int i=1;i<=n;++i) {
		pref[i]=pref[i-1]+a[dfs[i]];
	}
	for(int i=1;i<=m;++i) {
		int op,x,l,r;
		int64 v;
		is>>op;
		if(op==1) {
			is>>x>>v;
			Change(x,v);
		} else {
			is>>l>>r;
			qword Ans=Query(l,r);
			os<<Ans<<'\n';
		}
	}
	return 0;
}