Notice

  • “朋友们,虽然这个世界日益浮躁起来,只要能够为了当时纯粹的梦想和感动坚持努力下去,不管其它人怎么样,我们也能够保持自己的本色走下去。”
  • 愿不枉OI一场。
  • 需要的话,这里有旧文里面#include的“lucida”
  • 刚刚把和Mathjax打架的hexo-renderer-marked换成了hexo-renderer-pandoc,markdown语法更严格,而且一些公式被我手动加escape的符号严重影响了阅读。要改过来还是个大工程。

yist

\(\cdot\)对计数一窍不通。

Link

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

Solution

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

第一种情况,枚举\(c\),枚举\(d\),维护一个数组找\(a+b=d-c\)的方案数

第二种情况,有\(a<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;
}

3D计算几何的旋转与求交

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

旋转

已知点\(P=(x,y,z)\),把它沿着\(\overrightarrow a=(x_0,y_0,z_0)\)转动\(\theta^{\circ}\)(从与向量相对的角度看过去,点是逆时针旋转的) 首先可以给出绕三个轴的旋转矩阵 \[R_x(\theta)=\begin{bmatrix} 1&0&0\\ 0&\cos\theta&-\sin\theta\\ 0&\sin\theta&\cos\theta \end{bmatrix}\] \[R_y(\theta)=\begin{bmatrix} \cos\theta&0&\sin\theta\\ 0&1&0\\ -\sin\theta&0&\cos\theta \end{bmatrix}\] \(R_y\)有些不同,因为\(R_y\)的变化中\(z\)等价成了二维的\(x\)轴,\(x\)被等价成了\(y\)\[R_z(\theta)=\begin{bmatrix} \cos\theta&-\sin\theta&0\\ \sin\theta&\cos\theta&0\\ 0&0&1 \end{bmatrix}\]

对于这三个特殊的旋转轴我们已经有了解决方案了,那么对于任意的轴\(\overrightarrow a\)要怎么办呢?我们可以将这个旋转分解: 将整个坐标轴旋转,使得旋转轴\(\overrightarrow a\)\(z\)轴重合 再将点\(P\)\(z\)轴旋转\(\theta\)角 再将整个坐标轴旋转回原位

算了直接上结论。。Miskcoo \[\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}\] 还是很优美的。

线面相交

设平面的法向量为\(\overrightarrow n\),平面上有一点\(P\)。有直线\(l=Q+t\overrightarrow v\)

设交点为\(C\),则

\[\left\{ \begin{aligned} &(C-P)\cdot \overrightarrow n=0\\ &C=Q+t'\overrightarrow v \end{aligned} \right.\] 解得\(t'=\dfrac {(P-Q)\cdot\overrightarrow n}{\overrightarrow v\cdot\overrightarrow n}\)

\(\overrightarrow v\cdot\overrightarrow n\)的时候,显然交点不存在。

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

一道题

附上一道练手题目:Shadow

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

写完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;
}

BZOJ 4012 开店

Link

Solution 树链剖分套主席树

先不管颜色的限制 形式化条件:(\(len[x]\)\(x\)到根节点的距离) \(Ans=\sum\limits_{pos} len[u]+len[pos]-len[lca(pos,u)]\) 可以把\(len[u]\)\(len[pos]\)都提出来,答案就变成了计算\(\sum\limits_{pos}len[lca(pos,u)]\) 也就是\(u,pos\)到根节点路径的交集。这个可以通过先把每个点到根节点的路径都覆盖一遍,查询时候只需要统计出\(\sum v[e]coverCnt[e]\)即可。可以通过线段树实现。其中标记永久化的处理非常有意思。 套上了颜色的限制,就仿照序列主席树的做法,把点按照颜色排序,顺序依次覆盖。 空间上界是\(O(n\log^2 n)\)的,但是似乎跑不满。 时间是\(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(n\log^2n)\),空间\(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;
}

BZOJ 4336 骑士的旅行

Link

Solution

想了一种可持久化可并堆的做法,感觉空间要炸 再仔细想想: \(1\le K\le 20\)MDZZ!! # 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;
}

BZOJ 4009 接水果

Link

Solution

在树上画一画,可以发现路径覆盖的充分必要条件。 二维条件,转化成寻找覆盖一个点的权值第\(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
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;
}

BZOJ 2851 极限满月

Link

Solution

非常神奇的思路。 每个集合\(B_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;
}

BZOJ 2849 和谐串

Link

Solution

显然可以暴力DP。对小范围打表找规律可以得结论。 然后套Wallis公式 \(\dfrac {(2n)!!}{(2n-1)!!}\sim \sqrt{\pi n}\) \(Ans\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;
}

BZOJ 4765 普通计算姬

Link

Solution

\([1..n]\)这个答案序列分块!!为什么我总是想把树分块。。。 想到这,接着就比较好说了。 修改一个点对块的影响,是使得它在块内的祖先的权值都相应变化。块内的祖先个数,可以\(O(n\sqrt n)\)地预处理出来。 这样整块的统计是\(O(\sqrt n)\)的,那么零碎部分的也尽量\(O(\sqrt n)\),那就要求每个点的求值是\(O(1)\)的。显然常见套路树状数组做不到。 那么再用dfs序分块替代树状数组。同样支持区间修改,询问变成\(O(1)\),修改\(O(\sqrt n)\)。总复杂度就是\(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;
}

BZOJ 3131 淘金

Link

震惊!某ZZ OIer此题WA了半天竟是因为[点击查看]() # Solution 感觉第一步是最难想的。。但看了题解之后又觉得是很显然的。。只是不敢想罢了。 因为数字乘积的个数比较少,离散化一下就可以开到一维状态里。 然后一切都明朗了。 然而WA了很长时间,竟然因为 1. \(10^{12}\)居然是\(13\)位数?????? 2. 把数字分解的时候中间变量写成了int????

Tips

数据范围吓人的但是似乎比较显然的算法也不能不想。因为也许吓人的范围后面隐藏着一些可以减小范围的性质。 在可能爆int的题目中WA了,试试

1
#define int int64

不要数错数字位数。。。23333 # 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
#include "lucida"
using std::sort;
using std::unique;
using std::lower_bound;
using std::priority_queue;
const int P=1000000007,MAXCOUNT=203491+11,MAXINSCNT=11026+11;
int64 nums[MAXCOUNT];int nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
void DFS(int pos,int maxNumber,int64 prod) {
if(!pos) {
nums[++nc]=prod;
} else {
for(int d=maxNumber;d<10;++d) {
DFS(pos-1,d,prod*d);
}
}
}
void Prep() {
nums[nc=1]=0;//数组开小愣是看不着 233
DFS(13,1,1);
sort(nums+1,nums+1+nc);
nc=unique(nums+1,nums+1+nc)-nums-1;
}
struct Node {
int64 val;
int id,ext;
Node(int64 val,int id,int ext):val(val),id(id),ext(ext) {}
friend bool operator <(const Node &a,const Node &b) {
return a.val<b.val;
}
};
int main() {
freopen("input","r",stdin);
static int64 f[14][10][2][MAXINSCNT],g[MAXINSCNT];
Prep();
int64 n;int K;is>>n>>K;
//g[pos] 乘积为pos位置的个数
int bit[14],len=0;
for(int64 x=n;x;x/=10) {
bit[++len]=x%10;
}
for(int d=1;d<=bit[len];++d) {
f[len][d][d==bit[len]][ref(d)]=1;
}
for(int i=len-1;i;--i) {
for(int d=1;d<10;++d) {
f[i][d][0][ref(d)]=1;
}
}
for(int i=len-1;i;--i) {
for(int cd=1;cd<10;++cd) {
for(int pd=1;pd<10;++pd) {
for(int pu=0;pu<2;++pu) if(!(pu && bit[i]<cd)) {
for(int prod=1;prod<=nc;++prod) if(f[i+1][pd][pu][prod]) {
if(nums[ref(nums[prod]*cd)]!=nums[prod]*cd) {
throw;
}
f[i][cd][pu && cd==bit[i]][ref(nums[prod]*cd)]+=f[i+1][pd][pu][prod];
}
}
}
}
}
for(int prod=2;prod<=nc;++prod) {
for(int d=1;d<10;++d) {
for(int u=0;u<2;++u) if(!(u && bit[1]<d)) {
g[prod-1]+=f[1][d][u][prod];
}
}
}
nc--;
sort(g+1,g+1+nc);
priority_queue<Node> Q;
for(int i=1;i<=nc;++i) {
Q.push(Node(g[i]*g[nc],i,nc));
}
int64 Ans=0;
for(int i=1;i<=K && !Q.empty();++i) {
Node cur=Q.top();Q.pop();
(Ans+=cur.val)%=P;
if(cur.ext!=1) {
Q.push(Node(g[cur.id]*g[cur.ext-1],cur.id,cur.ext-1));
}
}
os<<Ans<<'\n';
return 0;
}


Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利