orangejuice's blog

挂了请务必叫我

Posted on Edited on In

「北大集训 2021」魔塔 OL | CTT2022 D1 T2

题目大意

维护 \(q\) 个操作：

  1. 在序列末尾新增一个点 \((x,y,z)\) ，其权值为 \((a,b)\) 。

  2. 删除序列中编号为 \(k\) 的点（不影响其他点编号）。

  3. 仅保留序列中三维分别在 \(g,l,d\) 以内的点，做询问：

    每一个点是一只怪物，击杀他需要 \(a\) 的血量，击杀后会恢复 \(b\) 的血量。

    求击杀当前序列中所有怪物需要的最少初始血量。

简要分析

先不考虑三维偏序的部分，对于序列 \(a_i,b_i\) 做贪心：

考虑相邻交换，若交换 \(i,j\ (j=i+1)\) 更优，则满足： \[ \max\{a_i,a_j+a_i-b_i\}>\max\{a_j,a_i+a_j-b_j\} \\ 即 (a_i>a_j \and a_i>a_i+a_j-b_j) \or (a_j+a_i-b_i>a_j \and a_j+a_i-b_i>a_i+a_j-b_j) \\ 即 (a_j-b_j<0 \and a_i>a_j) \or (a_i-b_i>0 \and b_j>b_i) \] 具体排序方式即：

  1. \(a_i-b_i<0\) 的放在前面，按照 \(a_i>a_j\) 排序。
  2. \(a_i-b_i>0\) 的放在后面，按照 \(b_j>b_i\) 排序。

连续的二元组 \((a_i,b_i)\) 容易合并为 \((a',b')\) ，分别为：最大值，总和。

离线所有点，按照上述方式排序，将得到的序列每 \(B\) 个分一块，每一个块维护所有 \(2^B\) 种情况对应的二元组和。

对于第 \(i\) 个块，维护 \(3\) 组集合：

  1. \(x\leq u\) 的集合 \(A_{i,u}\) 。
  2. \(y\leq v\) 的集合 \(B_{i,v}\) 。
  3. \(z\leq w\) 的集合 \(C_{i,w}\) 。

在操作时，动态维护集合 \(S\) 表示当前在整个序列里的点。

查询时对于每一个块，求出 \(S\ \cap A_{i,g}\ \cap B_{i,l}\ \cap C_{i,d}\) ，然后处理对应集合。

设 \(n\) 为怪物总数， \(x\) 为三维的值域，复杂度为 \(O(n\log n+\frac{nx}{B}+\frac{n\cdot 2^B}{B}+q\frac{n}{B})\)

\(B\) 大致取 \(\log n\) 即可。

ans[i]=(a,b)

[i,i+B)

Posted on Edited on In

「CEOI2020」象棋世界

下文默认 \(n=R,m=C,x=c_1,y=c_R\)

Pawn

略

Rook

略

Queen

先判掉一次到达的情况，然后就可以从起点和终点分别画出5条可行线

由此得到若干交点，手动数一下有几个交点在内部的整点上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void QQQ(){
	int d=abs(x-y);
	if(d==n-1 || d==0) puts("1 1"); // 一次到达
	else {
		d=(n-1-d)/2;
		int res=4;
		if(n==m) {
            // 一条斜着，一条平着
			if(x==1 || x==n) res++;
			if(y==1 || y==n) res++;
		}
		if(((x+1)&1)==((y+n)&1)) { // 先判断整点，然后判断两条斜线相交是否在内部
			if(min(x,y)-d>=1) res++;
			if(max(x,y)+d<=m) res++;
		}
		printf("%d %d\n",2,res);
	}
}

\[ \ \]

\[ \ \]

Bishop

看起来是很复杂的问题，但是实际上可以从一个简单的贪心入手

判定条件

可以发现，任意一次行走的直线上，坐标 \((x,y)\) 的 \((x+y)\mod 2\) 不变

所以只要 \(x+1\equiv y+n\pmod 2\) 即可

贪心策略

首先一定是每次向前走

第一步选择向左/右，然后每次转向，每次走都顶到边界线

但是这样显然会无法到达最终位置

纠正方法

考虑贪心到达的最后位置为 \(to\) ，那么得到的差值 \(|to-y|\) 是我们要矫正的距离

而矫正方法：在中途出现的每次转向位置，向里面"凹"进去一点，每凹进去一格，实际上相当于少走了两格

注意矫正的方向是根据最后一步走的方向而变化的，因此如果矫正方向不对，需要额外增加一步

此时，相当于需要多矫正到沿边界线对称的位置，需要多走 \(2(to-1)\) 或者 \(2(m-to)\) 的距离

假设走了 \(c\) 步，那么我们有 \(c-1\) 个转折点，最后将这若干的矫正距离分配到 \(c-1\) 个转折点上，可以用一个组合数解决

由于矫正距离是 \(O(m)\) 的，所以组合数显然可以在 \(O(m)\) 时间内求出

\[ \ \]

最后将向左向右合并即可

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
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int C(int n,int m) {
	if(m>n-m) m=n-m;
	int a=1,b=1;
	rep(i,1,m) a=1ll*a*(n-i+1)%P,b=1ll*b*i%P;
	return a*qpow(b)%P;
}
int Divide(int n,int m){ // Divide n elements in to m groups , each can be empty
	if(m<=0 && n>0) return 0;
	return C(n+m-1,m-1);
}
void BBB(){
	if(((x+1)&1)!=((y+n)&1)) return puts("0 0"),void();
	auto Subsolver=[&](int x,int y){
        // assume that we go left first
		int c=0,to=x,dis=n-1; // count , towardsposition
		c=1,dis-=x-1,to=1; // go left by x-1
		c+=dis/(m-1),to=((dis/(m-1))&1)?m:1,dis%=m-1; // then each step m-1 opposite
		if(dis) c++,to=to==1?to+dis:to-dis; // reach destination (NO!)
		if(to==y) return mp(c,1);
		int d=abs(to-y)/2;
		if((c&1)  && y>to) d+=to-1,c++;
		if((~c&1) && y<to) d+=m-to,c++;
		return mp(c,Divide(d,c-1));
	};
	Pii l=Subsolver(x,y),r=Subsolver(m-x+1,m-y+1);
	if(l.first>r.first) swap(l,r);
	if(r.first==l.first) (l.second+=r.second)%=P;
	printf("%d %d\n",l.first,l.second);
}

\[ \ \]

\[ \ \]

King

可以发现，每次一定是向前的三个方向走，由此可以得到一个简单的 $O(nm)$ \(dp\)

用矩阵优化可以做到 \(O(m^3\log n)\) 求出所有的答案

难点在于如果快速求出这个矩阵 \(A\) 的 \(A^{n-1}\) ，即要加速矩阵求幂

容易想到用 特征多项式 解决该问题，参考

问题分为两步

得到 \(p_m(\lambda)\)

列出我们的转移矩阵 \(A=\)

\(\begin{matrix}1\ 1\ 0\ 0\ 0\ 0\ \cdots \ 0\\ 1\ 1\ 1\ 0\ 0\ 0\ \cdots \ 0\\ 0\ 1\ 1\ 1\ 0\ 0\ \cdots \ 0\\ \cdots\cdots\cdots\cdots \\ 0\ \cdots\ 0\ 0\ 1\ 1\ 1\ 0\\0\ \cdots\ 0\ 0\ 0\ 1\ 1\ 1\\ 0\ \cdots\ 0\ 0\ 0\ 0\ 1 \ 1\end{matrix}\)

\(\lambda I-A=\)

\(\lambda -1\) \(-1\) \(0\) \(0\) \(0\) \(0\) \(\cdots\) \(0\)
\(-1\) \(\lambda -1\) \(-1\) \(0\) \(0\) \(0\) \(\cdots\) \(0\)
\(0\) \(-1\) \(\lambda -1\) \(-1\) \(0\) \(0\) \(\cdots\) \(0\)
\(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\)
\(0\) \(0\) \(\cdots\) \(0\) \(-1\) \(\lambda -1\) \(-1\) \(0\)
\(0\) \(0\) \(\cdots\) \(0\) \(0\) \(-1\) \(\lambda -1\) \(-1\)
\(0\) \(0\) \(\cdots\) \(0\) \(0\) \(0\) \(-1\) \(\lambda -1\)

每一行有 \(2/3\) 个元素，看起来并不是很好得到行列式

但是容易得到一个递推式，设 \(m\) 阶转移矩阵的特征多项式为 \(p_m(\lambda)\)

如果最后一行取第 \(m\) 个元素，值为 \((\lambda-1)p_{m-1}(\lambda)\)

如果最后一行取第 \(m-1\) 个元素，值为 \(-p_{m-2}(\lambda)\)

因而得到

\(p_m(\lambda)=\left\{\begin{aligned}1&& m=0\\ \lambda-1 && m=1\\ (\lambda-1)p_{m-1}(\lambda)-p_{m-2}(\lambda) && m>1\end{aligned}\right.\)

可以在 \(O(m^2)\) 的时间内暴力求出，也可以得到通项公式(太憨了)

那么得到关系用 \(\lambda^n\mod p_m(\lambda)\) 的系数优化计算，可以用暴力实现的多项式取模+快速幂得到 \(O(m^2\log n)\)

当然也可以优化

\[ \ \]

求出 \(A^0,A^1,A^2\cdots A^m\)

直接求显然是 \(O(m^3)\) 的，卡一卡说不定能过？

由于走的是一个 \(m\times m\) 的棋盘，可以用一个简单容斥得到答案

设 \(f_{x,y}\) 为从 \(x\) 走到 \(y\) ，中途允许超出边界的方案数

由于棋盘只有 \(m\times m\) ，中途最多只会可能经过一条边界线

而一旦在某一个时刻超出边界线到达 \(0/m+1\) ，那么接下来达到这条边界线两侧对称点的方案数是一样的

即：跨过了某一条边界线 \(0/m+1\) 的不合法方案数，可以用到达 \(y\) 关于这条边界线的 对称点的 不一定合法方案数得到

而不一定合法的 \(f_{x,y}\) 实际上只和 \(|x-y|\) 有关

由此，可以用 \(f_{0,i}\) 表示出 \(A^i_{x,y}\) ，那么接下来只需要先计算出 \(f_{0,i}\) 对于系数的求和，最终进行一次容斥，减去两侧不合法方案数即可

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
typedef vector <int> Poly;
Poly operator * (const Poly &a,const Poly &b){
	int n=a.size()-1,m=b.size()-1;
	Poly c(n+m+1);
	rep(i,0,n) rep(j,0,m) c[i+j]=(c[i+j]+1ll*a[i]*b[j])%P;
	return c;
}
Poly operator * (Poly a,const int &b){
	for(int &i:a) i=1ll*i*b%P;
	return a;
}
Poly operator + (Poly a,const Poly &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
Poly operator - (Poly a,const Poly &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
Poly operator % (Poly a,const Poly &b){
	int n=a.size()-1,m=b.size()-1;
	if(n<m) return a;
	assert(b[m]==1);
	drep(i,n-m,0) rep(j,0,m) a[i+j]=(a[i+j]+1ll*(P-a[i+m])*b[j])%P;
	a.resize(m);
	return a;
}
Poly Pow(Poly x,int k,Poly Mod){
	Poly res=x; k--;
	for(;k;k>>=1,x=x*x%Mod) if(k&1) res=res*x%Mod;
	return res;
}

Poly F,G,T=Poly{P-1,1};
int f[N*2],g[N*2],H[N*2];
void KKKInit(){
	G=Poly{1},F=T;
	rep(i,2,m) swap(F,G),F=G*T-F; // 递推特征多项式
	F=Pow(Poly{0,1},n-1,F); // 求出x^{n-1} mod p(x)
	f[0]=1,H[0]=F[0];
	rep(t,1,F.size()-1) { // 求出f_{0,i}，只需要求一半
		rep(i,0,t) g[i]=f[i];
		rep(i,0,t) {
			f[i]=(0ll+(i?g[i-1]:g[1])+g[i]+g[i+1])%P;
			H[i]=(H[i]+1ll*f[i]*F[t])%P; // 乘上系数累和
		}
	}
}
void KKK(){
	int res=H[abs(x-y)];
    // 两侧对称点
	// y -> 0-(y-0)=-y
	// y -> m+1+(m+1-y)=2(m+1)-y
	res-=H[abs(-y-x)];
	res-=H[abs(2*(m+1)-y-x)];
    // 容斥
	res=(res%P+P)%P;
	printf("%d %d\n",n-1,res);
}

Posted on Edited on In

[USACO 2020 February Platinum]Help Yourself

真的很套路。。。

考虑将区间 \((L_i,R_i)\) 按照左端点排序，依次考虑每个区间的贡献

令 \(dp_i\) 表示当前所有选择的右端点中最大的为 \(i\) 时的方案数

加入区间 \((L,R)\) 时

1.所有 \(i<L\) 的部分一定会断开成两个区间，转移时个数+1

2.当 \(i\ge L\) 时， \(dp_i\) 向 \(dp_{\max\lbrace R,i\rbrace}\) 转移，分两类讨论即可

不考虑个数的问题，直接转移是 \(O(n^2)\) 的，但是可以用线段树优化到 \(n\log n\)

(比较麻烦，需要实现区间查询，单点修改，区间乘法)

考虑个数 \(k\) 次幂，一种暴力的办法是存下 \(dp_{i,j}\) ，但是转移会变成 \(O(n^2\log n)\)

对于当前个数为 \(c\) 的情况，如果新增一个联通块，即变为 \(c+1\) ，答案由 \(c^k\) 变为 \((c+1)^k\)

考虑直接用二项式定理展开这个式子，需要记录 \(c^i(i\in [0,k])\) 的所有答案，再 \(O(k^2)\) 完成+1操作

结合线段树，维护 \(nk\) 个值，复杂度为 \(O(n(k\log n +k^2))\)

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define Mod1(x) ((x>=P)&&(x-=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,P=1e9+7;

int n,k;
Pii A[N];
int C[11][11];
int s[N<<2][11],res[11];
int t[N<<2];
void Up(int p) {
	rep(i,0,k) s[p][i]=s[p<<1][i]+s[p<<1|1][i],Mod1(s[p][i]);
}
void Down(int p) {
	if(t[p]==1) return;
	t[p<<1]=1ll*t[p<<1]*t[p]%P;
	t[p<<1|1]=1ll*t[p<<1|1]*t[p]%P;
	rep(i,0,k) {
		s[p<<1][i]=1ll*s[p<<1][i]*t[p]%P;
		s[p<<1|1][i]=1ll*s[p<<1|1][i]*t[p]%P;
	}
	t[p]=1;
}

void Que(int p,int l,int r,int ql,int qr) {
	if(ql<=l && r<=qr) {
		rep(i,0,k) res[i]+=s[p][i],Mod1(res[i]);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) Que(p<<1,l,mid,ql,qr);
	if(qr>mid) Que(p<<1|1,mid+1,r,ql,qr);
}

void Upd(int p,int l,int r,int ql,int qr) {
	if(ql<=l && r<=qr) {
		rep(i,0,k) s[p][i]*=2,Mod1(s[p][i]);
		t[p]*=2,Mod1(t[p]);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr);
	Up(p);
}
void Upd(int p,int l,int r,int x){
	if(l==r){
		rep(i,0,k) s[p][i]+=res[i],Mod1(s[p][i]);
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	x<=mid?Upd(p<<1,l,mid,x):Upd(p<<1|1,mid+1,r,x);
	Up(p);
}


int main(){
	n=rd(),k=rd();
	rep(i,1,n) A[i].first=rd(),A[i].second=rd();
	sort(A+1,A+n+1);
	rep(i,1,N*4-1) t[i]=1;
	rep(i,0,k) rep(j,C[i][0]=1,i) C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
	
	res[0]=1;
	Upd(1,0,n*2,0);

	rep(t,1,n) {
		int l=A[t].first,r=A[t].second;
		Upd(1,0,n*2,r,n*2);
		
		memset(res,0,sizeof res);
		Que(1,0,n*2,0,l-1);
		drep(i,k,0) rep(j,0,i-1) res[i]=(res[i]+1ll*C[i][j]*res[j])%P;
		Upd(1,0,n*2,r);

		memset(res,0,sizeof res);
		Que(1,0,n*2,l,r-1);
		Upd(1,0,n*2,r);
		
	}
	printf("%d\n",s[1][k]);
}

Posted on Edited on In

「APIO2018」选圆圈(K-D Tree/CDQ+Set)

Part1 K-D Tree做法

K-D Tree经常用来优化大暴力。。

把圆 \((x,y,r)\) 视为矩形 \((x-r,y-r,x+r,y+r)\) ，依据 \((x,y)\) 构建K-D Tree

维护K-D Tree每个节点所有矩形最小和最大的 \(x,y\) ，通过判断当前圆与其是否有交来剪枝

删去的节点 \(x,y\) 不算进矩形范围即可

很显然这是一个最坏 \(O(n^2)\) 的算法，直接 \(x,y\) 轮换建树这样写APIO的数据已经卡过了。。

比较好的办法是按照 \(x,y\) 的方差大的一维建树，当然旋转角度也是可以的

实际运行速度堪比 \(O(n\log n)\)

Code1:旋转+ \(x,y\) 轮换建树

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } 
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) f=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3e5+10,INF=1e9+10;
const db eps=1e-7;
const db co=cos(1123),si=sin(1123);

int n,typ;
struct Node{
	db x,y; int r,id;
}A[N],B[N];
db Dis(db x,db y,Node z){ return (x-z.x)*(x-z.x)+(y-z.y)*(y-z.y); }
db Dis(Node x,Node y){ return Dis(x.x,x.y,y); }
db In(db x,db y,Node z){ return Dis(x,y,z)-eps<=(db)z.r*z.r; }
int cmp(Node x,Node y){ return typ?x.x<y.x:x.y<y.y; }
int c[N],ch[N][2],rt;
db lx[N],rx[N],ly[N],ry[N];
void Up(int u) {
	if(c[B[u].id]) lx[u]=ly[u]=1e18,rx[u]=ry[u]=-1e18;
	else lx[u]=B[u].x-B[u].r,rx[u]=B[u].x+B[u].r,ly[u]=B[u].y-B[u].r,ry[u]=B[u].y+B[u].r;
	for(int v:ch[u]) if(v) cmin(lx[u],lx[v]),cmax(rx[u],rx[v]),cmin(ly[u],ly[v]),cmax(ry[u],ry[v]);
}
int Build(int l,int r) {
	if(l>r) return 0;
	int u=(l+r)>>1;
	nth_element(B+l,B+u,B+r+1,cmp);
	typ^=1; ch[u][0]=Build(l,u-1),ch[u][1]=Build(u+1,r); typ^=1;
	return Up(u),u;
}
int Cross(int x,Node y){
	if(lx[x]>rx[x]) return 0;
	if(In(lx[x],ly[x],y) || In(lx[x],ry[x],y) || In(rx[x],ly[x],y) || In(rx[x],ry[x],y)) return 1;
	if(lx[x]-eps<=y.x && y.x<=rx[x]+eps && ly[x]-eps<=y.y && y.y<=ry[x]+eps) return 1;
	if(lx[x]-eps<=y.x && y.x<=rx[x]+eps) if(In(y.x,ly[x],y) || In(y.x,ry[x],y)) return 1;
	if(ly[x]-eps<=y.y && y.y<=ry[x]+eps) if(In(lx[x],y.y,y) || In(rx[x],y.y,y)) return 1;
	return 0;
}
void Del(int u,Node x){
	if(!u || !Cross(u,x)) return;
	if(!c[B[u].id] && Dis(x,B[u])-eps<=(db)(x.r+B[u].r)*(x.r+B[u].r)) c[B[u].id]=x.id;
	Del(ch[u][0],x),Del(ch[u][1],x);
	Up(u);
}

int main(){
	n=rd();
	rep(i,1,n) {
		db x=rd(),y=rd();
		A[i]=B[i]=(Node){x*co-y*si,x*si+y*co,rd(),i};
	}
	sort(A+1,A+n+1,[&](Node x,Node y){ return x.r!=y.r?x.r>y.r:x.id<y.id;}),rt=Build(1,n);
	rep(i,1,n) if(!c[A[i].id]) Del(rt,A[i]);
	rep(i,1,n) printf("%d ",c[i]);
}

\[ \ \]

Code2:方差建树

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } 
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }
char buf[200000],*p1,*p2;
#define getchar() (((p1==p2)&&(p2=(p1=buf)+fread(buf,1,200000,stdin))),*p1++)
char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) f=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}
void wt(int x){
	static int buf[10],l=0;
	while(x) buf[++l]=x%10+'0',x/=10;
	drep(i,l,1) putchar(buf[i]);
	l=0;
}

const int N=3e5+10,INF=1e9+10;

int n,typ;
struct Node{
	ll x,y,r;
	int id;
}A[N],B[N];
ll Dis(ll x,ll y,Node z){ return (x-z.x)*(x-z.x)+(y-z.y)*(y-z.y); }
ll Dis(Node x,Node y){ return Dis(x.x,x.y,y); }
int In(ll x,ll y,Node z){ return Dis(x,y,z)<=z.r*z.r; }
int cmp(Node x,Node y){ return typ?x.x<y.x:x.y<y.y; }
int c[N],ch[N][2],rt;
int lx[N],rx[N],ly[N],ry[N];
void Up(int u) {
	if(c[B[u].id]) lx[u]=ly[u]=INF,rx[u]=ry[u]=-INF;
	else lx[u]=B[u].x-B[u].r,rx[u]=B[u].x+B[u].r,ly[u]=B[u].y-B[u].r,ry[u]=B[u].y+B[u].r;
	for(int v:ch[u]) if(v) cmin(lx[u],lx[v]),cmax(rx[u],rx[v]),cmin(ly[u],ly[v]),cmax(ry[u],ry[v]);
}

int Get(int l,int r){
	long double _x=0,_y=0,x=0,y=0;
	rep(i,l,r) _x+=B[i].x,_y+=B[i].y;
	_x/=r-l+1,_y/=r-l+1;
	rep(i,l,r) x+=(B[i].x-_x)*(B[i].x-_x),y+=(B[i].y-_y)*(B[i].y-_y);
	return x>y;
}

int Build(int l,int r) {
	if(l>r) return 0;
	int u=(l+r)>>1;
	typ=Get(l,r),nth_element(B+l,B+u,B+r+1,cmp);
	ch[u][0]=Build(l,u-1),ch[u][1]=Build(u+1,r);
	return Up(u),u;
}
int Cross(int x,Node y){
	if(lx[x]>rx[x]) return 0;
	if(In(lx[x],ly[x],y) || In(lx[x],ry[x],y) || In(rx[x],ly[x],y) || In(rx[x],ry[x],y)) return 1;
	if(lx[x]<=y.x && y.x<=rx[x] && ly[x]<=y.y && y.y<=ry[x]) return 1;
	if(lx[x]<=y.x && y.x<=rx[x]) if(In(y.x,ly[x],y) || In(y.x,ry[x],y)) return 1;
	if(ly[x]<=y.y && y.y<=ry[x]) if(In(lx[x],y.y,y) || In(rx[x],y.y,y)) return 1;
	return 0;
}
void Del(int u,Node x){
	if(!u || !Cross(u,x)) return;
	if(!c[B[u].id] && Dis(x,B[u])<=(x.r+B[u].r)*(x.r+B[u].r)) c[B[u].id]=x.id;
	Del(ch[u][0],x),Del(ch[u][1],x);
	Up(u);
}

int main(){
	n=rd();
	rep(i,1,n) {
		int x=rd(),y=rd();
		A[i]=B[i]=(Node){x,y,rd(),i};
	}
	sort(A+1,A+n+1,[&](Node x,Node y){ return x.r!=y.r?x.r>y.r:x.id<y.id;}),rt=Build(1,n);
	rep(i,1,n) if(!c[A[i].id]) Del(rt,A[i]);
	rep(i,1,n) printf("%d ",c[i]);
}

\[ \ \]

Part2 CDQ+Set

这是一个稳定 \(O(n\log ^2n)\) 的算法

按照 \(r\) 递减， \(id\) 递增的顺序对于圆排序后， \(CDQ\) 考虑 \([l,mid]\) 对 \([mid+1,r]\) 的贡献

先处理 \([l,mid]\) 的部分，就能知道哪些圆可以对 \([mid+1,r]\) 产生贡献

处理贡献时，依然把圆视为矩形，按照 \(x\) 插入、删除和查询矩形的左右边界 \((x-r,y),(x+r,y)\)

插入、删除和查询均是在 \(set\) 中维护 \(y\) 的前驱后继

同时还需要交换 \(x,y\) 重新进行一遍

正确性：

与每个圆交的圆一定在 \(x\) 或 \(y\) 上与它相邻

如果这个圆在x,y上都不与它相邻还与它相交，则必然会跨过一个相邻的圆，这个圆不会被加入set

故不存在这种情况

实际运行常数很大，被K-D Tree吊起来打

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(i=a;i<=b;++i)
using P=pair<int,int>;
#define M make_pair
#define X first
#define Y second
#define S(x) 1ll*(x)*(x)
const int N=1e6+10;
int n,c[N],i,j,D[N];
struct C{ int x,y,r,i; } A[N]; 
void Upd(int i,int j) { if(S(A[i].x-A[j].x)+S(A[i].y-A[j].y)<=S(A[i].r+A[j].r)&&D[c[A[j].i]]>i) c[A[j].i]=A[i].i; }
set<P>st;
P I[N],E[N],Q[N];
void Work(int l,int r){
	int mid=(l+r)>>1,n=0,m=0,x=0,y=0,t;
	rep(i,l,mid) if(c[A[i].i]==A[i].i) I[m]=M(A[i].x-A[i].r,i),E[m++]=M(A[i].x+A[i].r+1,i);
	rep(i,mid+1,r) Q[n++]=M(A[i].x-A[i].r,i),Q[n++]=M(A[i].x+A[i].r,i);
	sort(I,I+m),sort(E,E+m),sort(Q,Q+n),st.clear();
	rep(i,0,n-1) {
		while(x<m&&I[x].X<=Q[i].X) st.insert(M(A[t=I[x++].Y].y,t));
		while(y<m&&E[y].X<=Q[i].X) st.erase(M(A[t=E[y++].Y].y,t));
		auto j=st.lower_bound(M(A[t=Q[i].Y].y,t));
		if(j!=st.end()) Upd(j->Y,t);
		if(j!=st.begin()) Upd((--j)->Y,t);
	}
}
void Solve(int l,int r) {
	if(r-l+1<=80) {
		rep(i,l,r)if(c[A[i].i]==A[i].i)rep(j,i+1,r) Upd(i,j);
		return;
	}
	int mid=(l+r)>>1;
	Solve(l,mid);
	Work(l,r);rep(i,l,r) swap(A[i].x,A[i].y);
	Work(l,r);rep(i,l,r) swap(A[i].x,A[i].y);
	Solve(mid+1,r);
}
int main(){
	scanf("%d",&n);
	rep(i,1,n) scanf("%d%d%d",&A[i].x,&A[i].y,&A[i].r),A[i].i=i;
	sort(A+1,A+n+1,[&](C x,C y){return M(-x.r,x.i)<M(-y.r,y.i);});
	rep(i,1,n) D[A[i].i]=c[i]=i;
	Solve(1,n);
	rep(i,1,n) printf("%d ",c[i]);
}

Posted on Edited on In

「APIO2019」奇怪装置

找到循环就很简单了

很显然 \(y\) 是每 \(B\) 次一循环的，对于每个相邻的 \(y\) 循环 \(x\) 的值均相差 \(B+1 \pmod A\)

因此总的循环就是 \(B+1\) 对于 \(A\) 的循环乘上 \(B\)

即 \(\frac{A}{gcd(A,B+1)}\cdot B\)

知道循环节之后，把查询分成 \(O(n)\) 个区间，排序之后直接解决即可

如果使用基数排序即可做到 \(O(n)\)

以下是快排版本

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define mp make_pair
char IO;
ll rd(){
	ll s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}
int n,c,i;
ll A,B,ans,r=-1,L,R;
pair <ll,ll> S[2000010];
int main(){
	for(n=rd(),A=rd(),B=rd(),A=min(1.0*B*(A/__gcd(A,B+1)),1e18),i=1;i<=n;++i) {
		L=rd(),R=rd();
		if(R-L+1>=A) return printf("%lld\n",A),0;
		L%=A,R%=A;
		L<=R?S[++c]=mp(L,R):(S[++c]=mp(L,A-1),S[++c]=mp(0,R));
	}
	for(sort(S+1,S+c+1),i=1;i<=c;++i) if(r<=S[i].second) ans+=S[i].second-max(r,S[i].first-1),r=S[i].second;
	printf("%lld\n",ans);
}

Posted on Edited on In

「APIO2019」桥梁(询问分块+并查集)

询问每 \(S\) 个分块后，每次对于所有块内未被更改的边 及 所有询问 排序，然后依次加入并查集，这一部分复杂度为 \(O(m \frac{q}{S}(\log m+\alpha(n)))\)

对于 \(S\) 条被改变的边，对于每个询问分别考虑这些边的贡献，复杂度为 \(O(qS)\) ，由于涉及到并查集回撤的问题，可以使用按秩合并，复杂度为 \(O(qS\log S)\)

按照上面两步暴力实现，复杂度大概可以做到 \(O((m+q)\sqrt{q}\log n)\)

实际可行的优化有：

用平衡树实现排序，每次暴力遍历，第一部分复杂度降为 \(O(q\log m+m\frac{q}{S} \alpha(n))\)

由于最多访问到 \(O(S)\) 个联通块，第二部分用 \(dfs\) 遍历来实现，复杂度降为 \(O(q S \alpha(n))\) (遍历过程中要访问联通块编号)

复杂度可以降到约 \(O((m+q)\sqrt {q} \cdot \alpha(n))\)

以下是暴力实现的代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define pb push_back
char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=1e5+10;
int n,m,S,q,qc;
struct Edge{
	int u,v,w;
	bool operator < (Edge __) const { return w<__.w; }
} A[N],B[N],Q[N];
struct Node{ int t,w; };
vector <Node> G[N];
int uid[N],uc,fa[N],sz[N],ux[N],uy[N],rc,ans[N];
int Find(int x){ while(fa[x]!=x) x=fa[fa[x]]; return x; }
void Union(int x,int y){
	x=Find(x),y=Find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x,y);
	ux[++rc]=x,uy[rc]=y;
	fa[x]=y,sz[y]+=sz[x]; // 按秩合并用于回撤
}

int main(){
	n=rd(),m=rd();
	rep(i,1,m) A[i].u=rd(),A[i].v=rd(),A[i].w=rd();
	S=sqrt(3*(n+m));
	rep(i,1,q=rd()) {
		ans[i]=-1;
		int opt=rd(),x=rd(),y=rd();
		if(opt==1) G[x].pb((Node){i,y});
		else Q[++qc]=(Edge){i,x,y};
		if(qc%S==0 || i==q) {
			if(!qc) continue;
			int c=0;
			rep(i,1,m) if(!G[i].size()) B[++c]=A[i];
			else uid[++uc]=i;
			sort(B+1,B+c+1),sort(Q+1,Q+qc+1);
			rep(i,1,n) fa[i]=i,sz[i]=1;
			int p=c;
			drep(i,qc,1) {
				while(p && B[p].w>=Q[i].w) Union(B[p].u,B[p].v),p--;
				rc=0;
				rep(j,1,uc) {
					int x=uid[j],w=A[x].w;
					for(auto k:G[x]) if(k.t<=Q[i].u) w=k.w;
					else break; // 找到询问时这条边的权值
					if(w>=Q[i].w) Union(A[x].u,A[x].v);
				}
				ans[Q[i].u]=sz[Find(Q[i].v)];
				drep(j,rc,1) fa[ux[j]]=ux[j],fa[uy[j]]=uy[j],sz[uy[j]]-=sz[ux[j]];// 回撤
				rc=0;
			}
			rep(i,1,uc) A[uid[i]].w=G[uid[i]].rbegin()->w,G[uid[i]].clear();
			uc=qc=0;
		}
	}
	rep(i,1,q) if(~ans[i]) printf("%d\n",ans[i]);
}

Posted on Edited on In

#「联合省选 2020 A」组合数问题

题意：

求 \(\begin{aligned}\sum _{k=0}^nf(k)\cdot x^k\cdot C(n,k)\end{aligned}\)

显然要对于 \(f(k)\) 的每一项考虑，第 \(i\) 项的贡献

\(a_i\begin{aligned}\sum _{k=0}^nk^i\cdot x^k\cdot C(n,k)\end{aligned}\)

通用的 \(O(m^2)\)

后面的这个式子，考虑它的组合意义，假设当前有 \(n\) 个格子，每个格子被染了 \([0,x]\) 的颜色

\(x^k\cdot C(n,k)\) 即枚举有 \(k\) 个格子涂了 \([1,x]\) 的颜色，剩下涂了 \(0\) 的颜色

\(k^i\) 的组合意义即可重复地选了 \(i\) 次，每次选出的都是在 \([1,x]\) 颜色的格子的方案数

那么问题可以转化为强制每一次被访问的格子都是 \([1,x]\) ，其他的格子随便涂 \([0,x]\)

问题在于每次被访问的格子会重复，于是可以想到一个简单的转化，求出 \(i\) 次访问了 \(j\) 不同位置的方案数

即斯特林数 \(S(i,j)\) ，可以得到的是

\(\begin{aligned}\sum _{k=0}^nk^i\cdot x^k\cdot C(n,k)=\sum_{j=0}^iS(i,j)\cdot \frac{n!}{(n-j)!}\cdot x^j(x+1)^{n-j}\end{aligned}\)

实际上可以在 \(O(m^2)\) 递推斯特林数时就把 \(\frac{n!}{(n-j)!}\) 加入权值， \(x^j(x+1)^{n-j}\) 可以预处理出来

因此总复杂度就是 \(O(m^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
long long i,j,n,m,P,x,y,F[1010],Pow[1010],r,ans;
int qpow(int x,int k) { 
	for(r=1;k;k>>=1,x=1ll*x*x%P) if(k&1) r=r*x%P; 
	return r; 
}
int main(){
	freopen("problem.in","r",stdin),freopen("problem.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld",&n,&x,&P,&m,&y),F[0]=1,ans=qpow(x+1,n)*y%P;
	for(int i=0;i<=m;++i) Pow[i]=1ll*qpow(x,i)*qpow(x+1,n-i)%P;
	for(i=1;i<=m;++i) {
		long long res=0;
		for(j=i,scanf("%lld",&y);~j;--j) {
			F[j]=(F[j]*j+(j?F[j-1]*(n-j+1):0))%P; // 类似斯特林数的递推
			res=(res+F[j]*Pow[j])%P;
		}
		ans=(ans+res*y)%P;
	}
	printf("%lld",ans);
}

特殊的 \(O(m\log^2 m)\)

(注意以下仅限于口胡!)

假设可以把 \(f(k)\) 转化为下降幂多项式，依然枚举每一项考虑，那么每次要求的就是

\(\begin{aligned}\sum _{k=0}^nk^{\underline i}\cdot x^k\cdot C(n,k)=i!\sum _{k=0}^nC(k,i)\cdot x^k\cdot C(n,k)\end{aligned}\)

依然考虑组合意义

\(x^k\cdot C(n,k)\) 即枚举有 \(k\) 个格子涂了 \([1,x]\) 的颜色，剩下涂了 \(0\) 的颜色

\(C(k,i)\) 的组合意义不可重复地选了 \(i\) 次，每次选出的都是在 \([1,x]\) 颜色的格子的方案数

那么问题可以转化为强制每一次被访问的格子都是 \([1,x]\) ，其他的格子随便涂 \([0,x]\)

\(\begin{aligned}\sum _{k=0}^nk^{\underline i}\cdot x^k\cdot C(n,k)=i!\cdot C(n,i)\cdot x^i\cdot (x+1)^{n-i}\end{aligned}\)

(式子应该没有问题，但是下面都是口胡)

求解下降幂多项式需要多点求值，还要求很多逆元

然而对于非质数的 \(P\) ，我们求不出 \(i!\) 的逆元

(比较智障的搞法就是每次乘法都存下 \(P\) 的每个质因数个数，这样，做乘法的复杂度是 \(\log P\) ，但是不知道最后做出的答案是不是能保证因数个数 \(\ge 0\) )

对于 \(P\) 为质数的情况，用 \(\text{MTT}\) 做多项式转下降幂多项式的复杂度是 \(O(m\log^2 m)\)

(听说用转置原理优化的多点求值已经可以跑 \(10^6\) 啦?)

Posted on Edited on In

#「APIO2019」路灯 (K-D Tree / 树套树 / CDQ + 树状数组)

首先想到一个简单的问题转化

对于一个询问，联通的时间是若干连续的区间 \([L_i,R_i]\)

所有的 \(L_i,R_i+1\) 都是关键点，即由不连通变为联通的时间 和 由联通变为不连通的时间

把答案转化为 \(\sum R_i+1-L_i\) 即可

问题转化为对于当前的操作，找到它是那些询问的关键点

如果是合并操作，被合并的两个区间之间变得联通

如果是分裂操作，裂开的两个区间之间不再联通

可以用set维护上述区间，发现每次被更新的值都是一个二维区间

算上时间这一维，问题转化为一个类 三维偏序问题，但是题限制了内存

Part1 K-D Tree

限制了内存，很容易想到直接K-D Tree，实际运行也比较优秀

注意可以把要询问的点拿出来建出K-D Tree，每次区间修改即可

时间复杂度 \(O(n\sqrt n)\) ，空间复杂度 \(O(n)\)

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define pb push_back
typedef pair <int,int> Pii;
#define mp make_pair
void cmin(int &a,int b){ ((a>b)&&(a=b)); }
void cmax(int &a,int b){ ((a<b)&&(a=b)); }

char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}
const int N=3e5+10,INF=1e9;

int n,m,rt,col[N],opt[N],a[N],b[N];
char str[N];
set <pair <int,int> > st,tmp;
struct Node{ int x,y; } A[N];
int cmp1(Node a,Node b){ return mp(a.x,a.y)<mp(b.x,b.y); }
int cmp2(Node a,Node b){ return mp(a.y,a.x)<mp(b.y,b.x); }
int ch[N][2],lx[N],rx[N],ly[N],ry[N],s[N],t[N];
int Build(int l,int r,int d=0) { 
	if(l>r) return 0;
	int u=(l+r)>>1;
    nth_element(A+l,A+u,A+r+1,d?cmp2:cmp1);
	ch[u][0]=Build(l,u-1,d^1),ch[u][1]=Build(u+1,r,d^1);
	lx[u]=rx[u]=A[u].x,ly[u]=ry[u]=A[u].y;
	for(int i:ch[u]) if(i) cmin(lx[u],lx[i]),cmin(ly[u],ly[i]),cmax(rx[u],rx[i]),cmax(ry[u],ry[i]);
	return u;
}

void Upd(int x1,int x2,int y1,int y2,int u,int x) {
	if(!u || x1>rx[u] || x2<lx[u] || y1>ry[u] || y2<ly[u]) return;
	if(x1<=lx[u] && rx[u]<=x2 && y1<=ly[u] && ry[u]<=y2) return void(s[u]+=x);
	if(x1<=A[u].x && A[u].x<=x2 && y1<=A[u].y && A[u].y<=y2) t[u]+=x;
	for(int i:ch[u]) Upd(x1,x2,y1,y2,i,x);
}
int Que(Node x,int u,int d=0) {
	if(A[u].x==x.x && A[u].y==x.y) return s[u]+t[u];
	int y=ch[u][!(d?cmp2(x,A[u]):cmp1(x,A[u]))];
	return Que(x,y,d^1)+s[u];
}

int main(){
	n=rd(),m=rd();
	scanf("%s",str+1);
	rep(i,1,n) col[i]=str[i]-'0';
	rep(i,1,n+1) {
		int r=i;
		while(col[r]) r++;
		st.insert(mp(i,r));
		i=r;
	}
	rep(i,1,m) {
		scanf("%s",str+1);
		if(str[1]=='t') opt[i]=1,a[i]=rd();
		else opt[i]=2,a[i]=rd(),b[i]=rd(),tmp.insert(mp(a[i],b[i]));
	}
	n=0;
	for(auto it:tmp) A[++n]=(Node){it.first,it.second};
	rt=Build(1,n);
	rep(i,1,m) {
		if(opt[i]==1) {
			int x=a[i];
			if(col[x]) {
				auto it=st.upper_bound(mp(x,INF)); it--;
				int l=it->first,r=it->second;
				st.erase(it);
				st.insert(mp(l,x)),st.insert(mp(x+1,r));
				Upd(l,x,x+1,r,rt,i);
			} else {
				auto it=st.upper_bound(mp(x,INF)),tmp=it; it--;
				int l=it->first,r=tmp->second; 
				st.erase(it),st.erase(tmp);
				st.insert(mp(l,r)),Upd(l,x,x+1,r,rt,-i);
			}
			col[x]^=1;
		} else {
			int ans=Que((Node){a[i],b[i]},rt);
			auto it=st.upper_bound(mp(a[i],INF)); it--;
			if(it->second>=b[i]) ans+=i;
			printf("%d\n",ans);
		}
	}
}

Part2 树套树(没有代码)

由于已知查询的节点，树套树的内存可以优化到 \(O(n\log n)\)

把要询问的点拉出来，每次询问在第二维中有 \(\log n\) 次单点查询，所以需要被查询的位置一共只有 \(n\log n\) 个

把这些会被查询的位置拿出来建成 \(n\) 棵静态的线段树，更新就直接在这些静态的线段树上区间更新即可

时间复杂度 \(O(n\log ^2 n)\) ，空间复杂度 \(O(n\log n)\)

Part3 CDQ+树状数组

是常规写法，不会被限制内存

CDQ一维，排序一维，树状数组一维，参见三维偏序

Posted on Edited on In

「BalticOI 2020」小丑

Analysis

问题即考虑加入一个边集，判断是否是二分图

容易想到用带权并查集/LCT 之类的结构维护

考虑对于每个左端点/右端点 维护最长的有解区间 \(R_i/L_i\)

\(L_i,R_i\) 显然具有单调性

就可以 \(O(1)\) 完成查询

下文认为 \(n,m\) 同阶

Sol1 LCT

考虑尺取，同时用 \(\text{LCT}\) 暴力维护答案合法性，下面只讲 \(\text{LCT}\) 实现

考虑对于所有的边，优先加入树上，对于每一个环，只保留最后被删除的边

这样可以保证一条边被删除时，两个连通块之间没有边

同时，维护每一个连通块内的奇环边 最优集合 即可

复杂度为 \(O(n\log n)\) ，速度。。。。

Sol2 分治决策单调性/整体二分

考虑用并查集维护二分图，求出 \(R_i\) ，对于 \(i\in [l,r]\) ，已知答案区间为 \([L,R]\)

通过枚举来找到 \([l,r]\) 中答案分别为 \([L,mid),[mid,R]\) 的两部分的界点 \(p\)

为此我们加入 \([mid+1,m]\) 的边，然后依次加入 \([1,r]\) 的边，直到出现方案

直接维护复杂度显然是错的

因此考虑在分治过程中，保证分治 \([l,r],[L,R]\) 时， \([1,l-1],[R+1,m]\) 的边集已经加入

此时每次操作需要移动的范围在 \([l,r],[L,R]\) 以内

分治共 \(\log n\) 层，每层长度总和为 \(n\) ，因此移动次数为 \(O(n\log n)\)

由于需要维护简单的回撤操作，可以用按秩合并并查集，因此总复杂度为 \(O(n\log ^2n)\)

Loj Submission

Posted on Edited on In

「BalticOI 2020」混合物

题目大意：

对于给定的向量 \(\vec{O}=(x,y,z)\)

动态维护一个集合 \(S=\{(x_i,y_i,z_i)\}\)

求出最少用几个 \(S\) 中的元素能够 实数正系数 线性组合得到 \(O\)

考虑令 \(\displaystyle x'=\frac{x}{x+y+z},y'=\frac{y}{x+y+z}\) ，显然 \(x,y\) 能够完成组合， \(z\) 就一定成立

此时，问题转化为了一个平面问题，答案分为几种情况

  1. \(S\) 包含 \(O\) ，答案显然为1

  2. \(O\) 在 \(S\) 中两点构成的线段上，显然答案为2

  3. \(O\) 被某一个三角形包含，答案为3

4.无解

不妨令 \(T=\{P-O|P\in S\}\) ，此时

情况1即 \(T\) 包含原点

情况2即 \(T\) 中某两点与原点共线且在原点两端

情况3即 \(S\) 构成的凸包包含原点

因为只需要判断是否包含，所以其实和凸包并没有关系

考虑不包含的情况，则显然可以用一个 以原点为界的半平面 包住 \(S\) 中的所有点

因此可以维护每个点的极角，判断是否可以用半平面完全包含

实现上，完全包含可以认为是 \(\max-\min<\pi\)

或者是半平面跨过极角为 \(0\) 的位置，此时令 \(x,y\) 分别为 \(<\pi\) 最大值， \(>\pi\) 最小值

能包含即 \(x+2\pi-y<\pi\)

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
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,INF=1e9+10;
const db eps=1e-9,PI=acos((db)-1);

int n;
struct Node{
	db x,y;
	Node(){}
	Node(db x,db y):x(x),y(y){}
	Node operator - (const Node &t) const { return Node(x-t.x,y-t.y); }
	db angle(){ 
		db t=atan2(y,x);
		if(t<-eps) t+=2*PI;
		return t;
	}
} O,A[N];
Node Read() {
	db a=rd(),b=rd(),c=rd(),s=a+b+c;
	return Node(a/s,b/s);
}

int cnt1,cnt2;
char op[2];
struct cmp{ bool operator () (const db &x,const db &y) const { return x+eps<y; } };
multiset <db,cmp> st;
db Go(db x){
	x+=PI;
	if(x>=2*PI) x-=2*PI;
	return x;
}
void Ins(Node x){
	if(fabs(x.x)<eps && fabs(x.y)<eps) return void(cnt1++);
	db y=x.angle();
	if(st.find(y)==st.end() && st.find(Go(y))!=st.end()) cnt2++;
	st.insert(y);
}

void Del(Node x){
	if(fabs(x.x)<eps && fabs(x.y)<eps) return void(cnt1--);
	db y=x.angle();
	st.erase(st.find(y));
	if(st.find(y)==st.end() && st.find(Go(y))!=st.end()) cnt2--;
}

int main(){
	O=Read();
	rep(_,1,rd()) {
		scanf("%s",op);
		if(*op=='A') Ins(A[++n]=(Read()-O));
		else Del(A[rd()]);
		if(cnt1) puts("1");
		else if(cnt2) puts("2");
		else {
			int f=1;
			if(st.empty()) f=0;
			else {
				if(*st.rbegin()-*st.begin()<PI+eps) f=0;
				else {
					auto y=st.upper_bound(PI),x=y; x--;
					if(*x+2*PI-*y<PI+eps) f=0;
				} 
			}
			puts(f?"3":"0");
		} 
	}
}
0%