orangejuice's blog

挂了请务必叫我

Posted on Edited on In

COCI2016-2017 Contest#2 F

首先分析题意: 任意走都能在 \(k\) 步内结束，也就是说，一定可以在 \(k\) 步内封锁所有出路

注意游戏停止的条件是后手不能走，因此即使在 \(k\) 步封住了出路，下一轮依然要标记一个点

因此必须是 \(<k\) 的

设树根1的 \(dep=0\) ，第 \(i\) 层表示所有 \(dep=i\) 的节点

发现第 \(i\) 次操作，一定是从 \(i-1\) 层走到了 \(i\)

假设最后的封路决策在 \(i\) 层封掉了2个点，那么这个决策一定是不优的

因为在 \(i\) 层花2的时间一定不如在 \(i-1\) 层和 \(i\) 层各花1的时间

因此，问题可以转化为: 在 \(1-k\) 层每层选择一个点，判断是否存在一种方案使得选择完成后完全封死出路

显然在最优情况下，选择的点之间不会有祖先关系，并且我们可以删掉所有 \(dep>k\) 的点

因此可以写出一个 \(n\cdot 2^k\) 的 \(dp\)

由于最后要阻塞其实是阻塞所有的叶子( \(dep=k\) 的点)

因此考虑令选择每个节点是覆盖了一段叶子，将叶子按照 \(\text{dfs}\) 序从小到大依次标号，设选择 \(i\) 子树能覆盖叶子范围 \(L_i,R_i\)

因此按照 \(L_i\) 从小到大依次考虑每个节点，加入的转移就是

\(\begin{aligned} dep_i\notin S,dp_{L_i,S}\rightarrow dp_{R_i+1,S\cup \lbrace dep_i\rbrace }\end{aligned}\)

如果用bitset实现，时间/空间复杂度均为 \(O(n \cdot 2^{k-5})\)

如果直接 \(dp\) 显然。。。考虑缩小 \(k\) 的范围

推论1: 当 \(n< \frac{(k-1)\cdot (k+2)}{2}\) 时，一定有解

考虑一个浅显的贪心： 在第 \(i\) 层用 \(\leq i\) 的代价标记这层所有点

这个方法不可用的条件就是第 \(i\) 层的点个数 \(>i\) ，那么就有 \(n\ge 2+3+\cdots+k=\frac{(k-1)(k+2)}{2}\)

可以看到此时 \(k\) 的上界已经缩小到 \(O(\sqrt n)\) 级别，但由于实际常数，还是太大了

\[ \ \]

推论2: 当 \(n\leq k\cdot k\) 时，一定有解

假设删除原树的1节点，则我们决策的对象变为一片森林

考虑依次决策每一层，每次推进一层，都会把选择一棵树删除，并且当前森林所有顶端的节点删除

要求 \(k\) 次决策后森林为空

设森林第一层包含 \(d\) 个节点

此时一定存在一个子树大小 \(\ge \frac{n}{d}\)

删除这个子树后，规模变为 \(n-d-\frac{n}{d}+1\)

我们知道 \(d+\frac{n}{d}\ge 2\sqrt n\)

\(n-d-\frac{n}{d}+1\leq n-2\sqrt n+1=(\sqrt n-1)^2\)

因此得证

此时 \(k\) 的上界已经缩小到19，完全可以通过

带入优化的复杂度为 \(O(n\cdot 2^{15})\)

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
#include<bits/stdc++.h>

using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define reg register
#define pb push_back
#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;
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=410;

int n,m;
vector <int> G[N],Q[N];
int dep[N],L[N],R[N],cnt;

void pre_dfs(int u,int f) {
	dep[u]=dep[f]+1;
	if(dep[u]==m-1) { L[u]=cnt++,R[u]=cnt; return; }
	L[u]=cnt;
	for(int v:G[u]) if(v!=f) pre_dfs(v,u);
	R[u]=cnt;
}

bitset <1<<19> dp[401],rev[20];
int F[N]; 

int main(){
	n=rd(),m=rd();
	if(m*m>=n) return puts("DA"),0;
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	memset(dep,-1,sizeof dep),dep[0]=-2,pre_dfs(1,0);
	rep(i,1,n) if(~dep[i]) Q[L[i]].pb(i);
	dp[0][0]=1;
	rep(i,0,m-1) rep(j,0,(1<<m)-1) if(~j&(1<<i)) rev[i][j]=1;
	rep(i,0,cnt-1) 
		for(int v:Q[i]) {
			dp[R[v]]|=(dp[i]&rev[dep[v]])<<(1<<dep[v]);
		}
	puts(dp[cnt].count()?"DA":"NE");
}







Posted on Edited on In

COCI2016/2017 Contest#3 F Meksikanac

设 \(M=\max\lbrace X_p,Y_p\rbrace\)

分析:

给定的多边形很难直接处理

如果直接枚举平移位置，然后判断每个点是否在多边形内部

由于不是凸包，判断点的位置可以用1.射线法,2.转角判断是否是360

一次判断复杂度为 \(O(K)\) ，因此复杂度为 \(O(M^2\cdot N\cdot K)\) ，显然不可取

但是观察题目的条件，不管怎么移动，多边形都只包含一些整点

由于多边形内的整点只有 \(O(M^2)\) 个，如果能全部求出，直接匹配判断会方便很多，且复杂度降为 \(O(M^4)\)

那么如何求出多边形内部的整点?

做法1

考虑枚举每个点，暴力判断，复杂度为 \(O(M^2K)\)

做法2

考虑枚举 \(x\) 一维，像写扫描线一样，把所有合法的 \(y\) 扫描出来(跨过奇数次在内部)

复杂度为 \(O(MK\log K)\) 或者可能 \(O(MK)\)

\[ \ \]

优化

发现转化后，问题变为了 :

给定点集 \(A,B\) ，判断将 \(A\) 点集平移 \((dx,dy)\) 后，是否存在点与 \(B\) 中重合

考虑这个问题的一维情形:

在给定的数轴上的 \([0,M]\) 内部有 \(A,B\) 两个数集

那么出现重合的平移量即 \(B_i-A_j\) ，这个问题可以用一次卷积解决，复杂度为 \(O(M\log M)\)

\[ \ \]

类似的，将 \(x,y\) 两维压在一起，做类似的卷积就可以判断 \((dx,dy)\) 是否合法了

复杂度为 \(O(M^2\log M^2)=O(M^2\log M)\)

实现上的话，把 \((x,y)\) 变为 \(x\cdot (y_p+2)+y\) 即可

注意这里的减法向下溢出没有关系，因为溢出的部分恰好不会被调用到

\[ \ \]

综上，总复杂度为 \(O(KM+M^2\log 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
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define reg register
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(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)
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())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}
 
const int N=510,M=10010,P=998244353;
const double eps=1e-9;
 
int X,Y,D,n,m;
struct Point{
    int x,y;
    void Read(){ x=rd(), y=rd(); }
} A[M];
 
const int K=N*N*4.2;
int F[K],G[K];
double U[M];
int cnt,rev[K];
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;
}
void NTT(int n,int *a,int f){
    static int e[K>>1];
    rep(i,1,n-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
    e[0]=1;
    for(int i=1;i<n;i<<=1) {
        int w=qpow(f==1?3:(P+1)/3,(P-1)/i/2);
        for(int j=i-2;j>=0;j-=2) e[j+1]=1ll*(e[j]=e[j>>1])*w%P;
        for(int l=0;l<n;l+=i*2) {
            for(int j=l;j<l+i;++j) {
                int t=1ll*a[j+i]*e[j-l]%P;
                a[j+i]=a[j]-t,Mod2(a[j+i]);
                a[j]+=t,Mod1(a[j]);
            }
        }
    }
    if(f==-1) {
        ll base=qpow(n);
        rep(i,0,n-1) a[i]=a[i]*base%P;
    }
}
 
void Cover(int x,int y){
    F[(X+1-x)*D+Y-y]=1;
}
 
 
int main(){
    X=rd(),Y=rd(),D=Y+2;
    rep(i,1,n=rd()) {
        int x=rd(),y=rd();
        G[x*D+y]=1;
    }
    int mix=1e9,miy=1e9,max=-1e9,may=-1e9;
    rep(i,1,m=rd()) {
        A[i].Read();
        cmin(mix,A[i].x),cmax(max,A[i].x);
        cmin(miy,A[i].y),cmax(may,A[i].y);
    }
    max-=mix,may-=miy;
    if(max>X || may>Y) return puts("0"),0;
    rep(i,1,m) A[i].x-=mix,A[i].y-=miy;
    A[m+1]=A[1];
    rep(i,0,X) {
        cnt=0;
        rep(j,1,m) {
            Point L=A[j],R=A[j+1];
            if(L.x>R.x) swap(L,R);
            if(i<L.x || i>R.x) continue;
            if(L.x==R.x) {
                rep(y,min(L.y,R.y),::max(L.y,R.y)) Cover(i,y);
                continue;
            }
            double y=1.0*(R.y-L.y)/(R.x-L.x)*(i-L.x)+L.y;
            if(i<R.x) U[++cnt]=y;
            if(abs(y-int(y))<eps) Cover(i,y);
        }
         
        sort(U+1,U+cnt+1);
        for(int j=1;j<=cnt;j+=2) for(int y=ceil(U[j]);y<=U[j+1]+eps;++y) Cover(i,y);
    }
 
    int R=1,cc=-1;
    while(R<=(X+1)*2*D) R<<=1,cc++;
    rep(i,1,R-1) rev[i]=(rev[i>>1]>>1)|((i&1)<<cc);
    NTT(R,F,1),NTT(R,G,1);
    rep(i,0,R-1) F[i]=1ll*F[i]*G[i]%P;
    NTT(R,F,-1);
    int ans=0;
    rep(i,0,X-max) rep(j,0,Y-may) if(!F[(X+1+i)*D+Y+j]) ans++;
    printf("%d\n",ans);
}

Posted on Edited on In

COCI2011/2012 Contest#1 F 状压加速dp

首先是一个非常Naive的dp，令 \(dp[i][x][y]\) 表示 \(i\) 时刻 \(x,y\) 是否能被跳到

枚举，然后转移，如果滚动数组，就可以做到 \(O(n^2)\) 空间， \(O(Tn^2)\) 时间复杂度

这显然是TLE的。。。

\[ \ \]

注意到题目的 \(n\leq 30\) ，可以直接用一个int存在某一行/列的答案

设时刻 \(i\) 第 \(j\) 列的答案为 \(dp[i][j]\)

假设不考虑答案的限制，两之间转移可以做到 \(O(1)\) ，即

  1. \(dp[i][j\pm 1]\) 左/右移两位

  2. \(dp[i][j\pm 2]\) 左/右移一位

两者转移即可，但是涉及到倍数的限制，设 \(can[i][j]\) 为 \(i\) 时刻 \(j\) 列的可行跳跃位置

则只需要最后的时候让 \(dp[i][j]\) 与 \(can[i][j]\) 取交集即可

如果直接枚举倍数，复杂度上限是 \(O(n^2 T)\)

考虑分块决策，设将 \([1,D]\) 的因数挑出来额外记录一个数组 \(can2[x][j]\) 表示值为 \(x\) 的第 \(j\) 列有那些

不直接枚举他们，而是在每次访问时考虑他们对于 \(can[i][j]\) 的贡献

在优秀实现下，复杂度上限为 \(O(n^2\frac{T}{D+1}+T (D+\sum_{t=1}^{D} \frac{1}{t} n))=O(n^2\frac{T}{D+1}+T (n\ln D+D))\)

这个实现上来说，就是枚举时间 \(i\) 后，判断是否满足 \(t|i\) ，然后再将 \(can2[t][j]\) 贡献到 \(can[i][j]\)

显然， \(t|i\) 成立的次数就是 \(T\sum_{t=1}^{D} \frac{1}{t}\) ，也就是要循环这么多次取贡献 \(j\) 这一维

调整一下 \(D\) 的参数

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
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define reg register
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
const int N=30,D=7;

int n,m,a[N][N],dp[2][N];
int can[1000010][N],t[D+1][N];

int main(){
	scanf("%d%d",&n,&m);
	int sx,sy; scanf("%d%d",&sx,&sy),sx--,sy--;
	rep(i,0,n-1) rep(j,0,n-1) {
		scanf("%d",&a[i][j]);
		if(a[i][j]<=D) t[a[i][j]][i]|=1<<j;
		else for(reg int T=a[i][j];T<=m;T+=a[i][j]) can[T][i]|=1<<j;
	}
	int cur=0; dp[cur][sx]=1<<sy;
	rep(i,1,m) {
		rep(j,1,D) if(i%j==0) rep(k,0,n-1) can[i][k]|=t[j][k];
		rep(j,0,n-1) {
			dp[!cur][j]=0;
			if(j) {
				dp[!cur][j]|=dp[cur][j-1]<<2;
				dp[!cur][j]|=dp[cur][j-1]>>2;
			}
			if(j<n-1) {
				dp[!cur][j]|=dp[cur][j+1]<<2;
				dp[!cur][j]|=dp[cur][j+1]>>2;
			}
			if(j>1) {
				dp[!cur][j]|=dp[cur][j-2]<<1;
				dp[!cur][j]|=dp[cur][j-2]>>1;
			}
			if(j<n-2) {
				dp[!cur][j]|=dp[cur][j+2]<<1;
				dp[!cur][j]|=dp[cur][j+2]>>1;
			}
			dp[!cur][j]&=can[i][j];
		}
		cur^=1;
	}
	int ans=0;
	rep(i,0,n-1) rep(j,0,n-1) if(dp[cur][i]&(1<<j)) ans++;
	printf("%d\n",ans);
	rep(i,0,n-1) rep(j,0,n-1) if(dp[cur][i]&(1<<j)) printf("%d %d\n",i+1,j+1);
}






Posted on Edited on In

COCI20162017 Contest#6 F

其实这个题不是很难的。。。

设值域为 \(M\)

考虑如果没有幸运数的限制，那么从 \(A\) 变成 \(B\) ，实际上只与 \(\frac{A}{B}\) 有关

不妨令 \(dp_{i,j}\) 为从 \(i\) 走了 \(j\) 步变成1，显然这个 \(j\) 的最大值为 \(\log M=19\) ，即 \(2^{19}\) 最多操作19次

从 \(i\) 枚举倍数进行转移，同时也暴力处理每个数的因数个数，复杂度为 \(O(M\ln M\log M)\)

\[ \ \]

接下来考虑幸运数的限制

推论: 最多只会在一个幸运数上停留

如果经过多个，显然在代价最小的那个上面停留

因此考虑枚举停留的幸运数 \(x\)

那么转移可以分为两步 \(\frac{A}{x}\) 和 \(\frac{x}{B}\) ，可以暴力合并两个 \(dp\) 数组，单次查询复杂度为 \(O(T\cdot \log^2 M)\)

合并得到的结果，可以描述为:

可以在 \(x\) 上用 \(C(x)\) 的代价停留，并且其他部分的转移花了 \(j\) 的时间， \(y\) 的代价

如果考虑停留的时间，那么得到的答案显然是一条直线，斜率就是停留的代价

关于一群直线，一群查询，不难想到可以斜率优化求解，这一部分复杂度为 \(O(T\log M\log (T\log M)+m)\) （排序复杂度）

总复杂度可以认为就是 \(O(M\log^2 M+Q(T\log ^2 M+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
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
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
#define reg register
#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,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

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=1e6+10,INF=1e9;

int n,m;
int F[N],A[N],B[N];
int L[N];
// A: 因子个数
// B: 将B变成1需要的最大步数
int C[N],D[N];
int dp[N][20];
// 用了j步，将i变为1的最小代价

struct Node{ 
    // 描述一条直线
	ll x,y;
	// 答案为 x*i+y
	ll operator [](const ll i)const {
		return i*x+y;
	} //求直线点值
	bool operator < (const Node __) const {
		if(x!=__.x) return x<__.x;
		return y<__.y; //按照斜率排序
	}
} U[N];

int Uc,T[21],R[21];

int main(){
	rep(i,1,N-1) {
		A[i]++;
		for(reg int j=i+i;j<N;j+=i) A[j]++,cmax(B[j],B[i]+1);
	}
	rep(i,1,rd()) F[i]=rd();
	rep(i,1,m=rd()) L[i]=rd();
	sort(L+1,L+m+1);
	rep(i,1,N-1) rep(j,0,B[i]) dp[i][j]=INF;
	dp[1][0]=0;
	rep(i,1,N-1) rep(j,0,B[i]) if(dp[i][j]<INF) for(reg int k=i+i;k<N;k+=i) cmin(dp[k][j+1],dp[i][j]+F[A[k/i]]);
	rep(i,1,n=rd()) C[i]=rd(),D[i]=rd();

	rep(kase,1,rd()) {
		int x=rd(),y=rd(),d=x/y;
		if(x%y!=0){
			printf("%d\n",-m);
			continue;
		}
		memset(R,63,sizeof R);
		Uc=0;
		rep(i,1,n) if(x%C[i]==0 && C[i]%y==0){
			int dx=x/C[i],dy=C[i]/y;
			memset(T,63,sizeof T);
			rep(a,0,B[dx]) if(dp[dx][a]<INF) rep(b,0,B[dy]) cmin(T[a+b],dp[dx][a]+dp[dy][b]);
			rep(j,0,B[dx]+B[dy]) if(T[j]<INF) {
				ll a=D[i],b=T[j]-a*j;
				U[++Uc]=(Node){a,b};
				rep(k,j,B[d]) cmin(R[k],(int)U[Uc][k]);
			}
		}
		rep(i,0,B[d]) cmin(R[i],dp[d][i]);
		ll ans=0;
		ll mi=1e18;
		sort(U+1,U+Uc+1);
		int R=0;
		rep(i,1,Uc) {
			if(mi<U[i].y) continue;
			mi=U[i].y;
			while(R>1 && (U[i].y-U[R].y)*(U[R].x-U[R-1].x)<=(U[R].y-U[R-1].y)*(U[i].x-U[R].x)) R--;
			U[++R]=U[i]; // 单调栈处理凸包，注意加入时满足x递增，y递减
		}
		rep(i,1,m) if(L[i]<=B[d]) ans+=::R[L[i]]<INF?::R[L[i]]:-1;
		else {
			while(R>1 && U[R-1][L[i]]<=U[R][L[i]]) R--;
			if(!R) ans--;
			else ans+=U[R][L[i]];
		}
		printf("%lld\n",ans);
	}
}

Posted on Edited on In

ARC117 - Tricolor Pyramid

设三种颜色分别为01,2, 容易发现原题变换 \(f(a,b)\) 的等价表达为

\(f(a,b)=(-a-b)\mod 3\)

\(\mod 3\) 可以最后处理，那么就是一个取负操作

看成一个递推 \(F_{n,i}=col_i\)

\(F_{i,j}=-F_{i+1,j}-F_{i+1,j+1}\) ，求出 \(F_{1,1} \mod 3\)

那么对于每个 \(col_i\) ，处理其对于 \(F_{1,1}\) 的贡献系数，容易发现贡献就是一个两边走的杨辉三角，即 \(\displaystyle \binom{n-1}{i-1}(-1)^{n-1}\)

然后我就真的暴力处理组合数

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
const int N=1e6+10,INF=1e9+10;

int n;
char s[N];
char ch[]="BWR";

int F[N],cnt[N];
int C(int n,int m){
	if(cnt[n]-cnt[m]-cnt[n-m]) return 0;
	return F[n]*F[m]*F[n-m]%3;
}

int main(){
	rep(i,F[0]=1,N-1) {
		cnt[i]=cnt[i-1],F[i]=F[i-1];
		int x=i;
		while(x%3==0) x/=3,cnt[i]++;
		F[i]=F[i]*x%3;
	}
	scanf("%d%s",&n,s+1);
	int sum=0;
	rep(i,1,n) {
		int t=0;
		if(s[i]=='W') t=1;
		if(s[i]=='R') t=2;
		if(~n&1) t=3-t;
		sum=(sum+C(n-1,i-1)*t)%3;
	}
	sum%=3,putchar(ch[sum]);
}

Posted on Edited on In

COCI20162017 Contest#7 F

前置知识

沿用上面的定义，设字符串 \(S\) 的 \(\text{border}\) 集合为 \(B(S)\)

考虑对于单串 \(S\) 求答案，设答案为 \(Ans\)

将所有可能出现的字符串分为两个集合 \(A,B\)

其中 \(A\) 为所有恰好出现 \(S\) 的字符串集合， \(B\) 为所有还未出现匹配的字符串集合

我们知道每个字符串出现有一定的概率，即为 \(\frac{1}{n^{|T|}}\)

设 \(A\) 集合中所有长度为 \(i\) 的串出现的概率总和为 \(A_i\) ，同理得到 \(B_i\)

\(A\) 中的概率是不重复的，因为每个匹配过程只有一次会恰好匹配，因此可以得到 \(\sum A_i=1\)

(而 \(B\) 中每个不匹配的串概率会被算多次)

最后的答案期望可以表示为

1.每个匹配的串概率*匹配时串的长度之和，即 \(Ans=\sum_i i\cdot A_i\)

2.将匹配成功的长度，转化为匹配失败的次数之和(包含空串)，可以表示为 \(Ans=\sum B_i\)

直接计算似乎比较麻烦

\[ \ \]

考虑如果在 \(B\) 中所有字符串的后面接上一个原串 \(S\) （同时概率乘上 \(\frac{1}{n^{|S|}}\) ），那么得到的新字符串一定完成匹配

但是实际上，这样的串并不一定完全合法，因为可能在更早的位置出现匹配

由上面的定义，假设原先在 \(B\) 中的串为 \(T\) ，原先已经在 \(S\) 中匹配了 \(T'\) 作为前缀

那么直接强行加上 \(S\) 后，如果 \(T'\) 会影响第一个出现匹配位置，设出现匹配时加入的字符串为 \(R\)

则显然满足: \(R\) 即是 \(S\) 的一段前缀，又是 \(S\) 的一段后缀，也就是 \(R\in B(S)\)

而剩下部分( \(|S|-|R|\) )，实际上是无效的，因此概率会被算小了

\[ \ \]

不妨设 \(B\) 集合接上一个 \(S\) 串得到的集合为 \(C\)

可以把 \(C\) 中的字符串，按照多余的部分 \(|S|-|R|\) 为多个部分 \(D_{R}\) 其中 \(R\in B(S)\)

发现，实际上去掉多余的部分后，每个 \(D_R\) 集合就与 \(A\) 集合对应，但是多余部分的要乘回去

即 \(A_i=D_{|R|,i+|S|-|R|}\cdot n^{|S|-|R|}\) (偏移多出的部分)

由 \(B,C\) 的关系，有 \(\sum_R D_{R,i}=C_i=B_i\cdot \frac{1}{n^{|S|}}\)

也就是 \(B_i\frac{1}{n^{|S|}}=\sum _R D_{R,i+|S|-|R|}=\sum _R \frac{A_{i+|S|-|R|}}{n^{|S|-|R|}}\)

即 \(B_i=\sum _R A_{i+|S|-|R|}n^{|R|}\)

将上式求和对于 \(i\) 求和，得到 \(\sum B_i=\sum_i\sum_R A_{i+|S|-|R|}n^{|R|}\)

由于 \(\sum A_i=1\) ( \(\sum A_i\) 和 \(\sum A_{i+|S|-|R|}\) 等价)， 即

\(Ans=\sum B_i=\sum_{R\in B(S)} n^{|R|}\)

Posted on Edited on In

[COCI2010-2011#2] CRNI(单调栈)

问题分析

首先考虑两个不相交的矩形可能存在的位置关系，我将其分成

1.左右

2.上下

3.左上右下

4.左下右上

发现1,2,3,4之间有相交,考虑四种情况的答案应该是1+2-3-4

统计方法

核心: 统计以一个点作为顶点的矩形数量

以统计 \(i,j\) 为右下角的矩形为例，先不考虑矩形大小>1的限制

显然可以在线性时间内处理得到每个 \(i,j\) 向上连续延伸的连续1长度，设其为 \(U_{i,j}\)

假设枚举了 \(i\) ，从左到右依次扫描 \(j\) ，则得到 \(i,j\) 位置的答案应该是

\[\begin{aligned} \sum_{k=1}^{j} \min_{d=k}^j\lbrace U_{i,d}\rbrace\end{aligned} \]

这条式子中，相当于枚举了 \(i,(k,j)\) 为底，统计向上延伸的最长长度

这个式子可以用单调栈在线性时间内求解，其过程可以描述为

1.每次插入元素 \(U_{i,j}\) ，得到它的影响区间 \(k\in [L,j]\)

2.将原先单调栈内 \(k\in [L,j]\) 这段区间的答案减掉，改为 \(U_{i,j}\cdot (j-L+1)\)

类似的，可以通过改变循环顺序和额外记录向下延伸的长度 \(D_{i,j}\) 来统计四种顶点的答案(详细见代码)

然后可以用前缀和帮助统计以上4种答案，枚举一个端点，另一个查询前缀和即可

tips: 注意累和顺序，前缀和要开long long

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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=1e3+10;

int n;
char a[N][N];
int D[N][N],U[N][N]; //i,j向下/上延伸的最长长度
int stk[N],c[N],top;
int CRR[N][N]; // 以i,j为右下角的矩形个数
int CLL[N][N]; // 以i,j为左上角的矩形个数
int CLR[N][N]; // 以i,j为右上角的矩形个数
int CRL[N][N]; // 以i,j为左下角的矩形个数
ll SLL[N][N],SRL[N][N]; // 前缀和

int main(){
	n=rd();
	rep(i,1,n) scanf("%s",a[i]+1);
	rep(i,1,n) rep(j,1,n) if(a[i][j]=='C') U[i][j]=U[i-1][j]+1;
	drep(i,n,1) rep(j,1,n) if(a[i][j]=='C') D[i][j]=D[i+1][j]+1;
	rep(i,1,n) {
		// 统计四种端点的情况
		top=0;
		int now=0;
		rep(j,1,n) {
			int x=U[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CRR[i][j]=max(now-1,0);
		}

		now=top=0;
		rep(j,1,n) {
			int x=D[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CLR[i][j]=max(now-1,0);
		}

		now=top=0;
		drep(j,n,1) {
			int x=U[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CRL[i][j]=max(now-1,0);
		}

		now=top=0;
		drep(j,n,1) {
			int x=D[i][j],cnt=1;
			while(top && stk[top]>=x) cnt+=c[top],now-=c[top]*stk[top],top--;
			stk[++top]=x,c[top]=cnt; now+=x*cnt;
			CLL[i][j]=max(now-1,0);
		}
	}

	drep(i,n,1) drep(j,n,1) SLL[i][j]=SLL[i+1][j]+SLL[i][j+1]-SLL[i+1][j+1]+CLL[i][j];
	rep(i,1,n) drep(j,n,1) SRL[i][j]=SRL[i-1][j]+SRL[i][j+1]-SRL[i-1][j+1]+CRL[i][j];
	// 前缀和

	ll ans=0;
	rep(i,1,n) rep(j,1,n) if(CRR[i][j]) ans+=CRR[i][j]*(SLL[i+1][1]+SLL[1][j+1]-SLL[i+1][j+1]);
	rep(i,1,n) rep(j,1,n) ans-=CLR[i][j]*SRL[i-1][j+1];
	// 统计4种情况
	printf("%lld\n",ans%10007);
}



Posted on Edited on In

何以伊名始

本题现已知四种做法，如果不会后缀系列结构可以直接看Solution4

设初始树大小和查询总长均为 \(O(n)\)

Solution1

由于查询只有1e6，因此出现的不同查询串长度最多 \(\sqrt {10^6}=1000\) 种

考虑对于每一种做一次dfs，在 \(\text{Hash Table}\) 中查询，复杂度为 \(O(n\sqrt n)\)

Solution2

将树上节点后缀排序，然后每次插入需要询问的字符就二分后缀区间

预处理复杂度为 \(O(n\log n)\) ，查询涉及二分和倍增，复杂度为 \(O(n\log ^2 n)\)

Solution3

给定的树看做trie树，可以对于trie树建广义后缀自动机，然后倒着让询问串去匹配，一旦失配答案为0，

需要预处理 \(link\) 树的子树和，时间复杂度为 \(O(n)\) ，空间复杂度为 \(O(n|\Sigma|)\)

Solution4

将询问的串倒着插入，构建AC自动机

由于AC自动机预处理，时间空间复杂度为 \(O(n|\Sigma|)\)

然后考虑对于树上每一个前缀在AC自动机上匹配，每次从父亲转移过来，复杂度为 \(O(n)\)

然后是常见的AC自动机操作， \(fail\) 树上的子树累和即可

需要询问离线，因此有一定局限性

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
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#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;
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=1e6+10;

int n,m,len,F[N],A[N];
char s[N],t[N];
int nxt[N][26],fail[N],cnt,pos[N];
int Q[N],L=1,R;
void Build(){
	rep(i,0,25) if(nxt[0][i]) Q[++R]=nxt[0][i];
	while(L<=R) {
		int u=Q[L++];
		rep(i,0,25) {
			int &v=nxt[u][i];
			if(v) fail[v]=nxt[fail[u]][i],Q[++R]=v;
			else v=nxt[fail[u]][i];
		}
	}
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) scanf("%c",s+i),F[i]=rd();
	rep(i,1,m) {
		scanf("%s",t+1);
		int now=0;
		drep(j,strlen(t+1),1) {
			int c=t[j]-'A';
			if(!nxt[now][c]) nxt[now][c]=++cnt;
			now=nxt[now][c];
		}
		pos[i]=now;
	}
	Build();
	rep(i,1,n) A[F[i]=nxt[F[F[i]]][s[i]-'A']]++;
	drep(i,R,1) A[fail[Q[i]]]+=A[Q[i]];
	rep(i,1,m) printf("%d\n",A[pos[i]]);
}

Posted on Edited on In

[COCI2010-2011#7] UPIT

约定:视 \(n,q\) 同阶

看一下题目的操作

1.区间赋值

2.区间差分加

3.插入元素

4.区间查询

我们知道1,2操作都是可以用懒标记维护的，具体过程可能有一点细节

1.记录区间差分加的过程，要记录等差数列首项和公差，两个等差数列相加直接首项和公差都相加即可

2.区间赋值的优先级要高于加法，即打上赋值标记就要清空加法标记，标记下传时注意先下传赋值标记

然后具体问题落到如何实现插入元素这个操作上

块状链表

对于静态的数组，可以直接静态分块来做

而要动态插入时，找到对应块，插入即可，但是涉及到编号问题

所以需要每个块维护一个 \(Size\) ，块内每个元素维护一个标号 \(id_i\)

同时需要对于块的 \(Size\) 累前缀和 \(SumSize\) ，则块 \(i\) 内编号为 \(j\) 的元素在数组中的实际编号为 \(SumSize_{i-1}+j\)

插入时把整个块内的元素取出重新标号即可

但是这样插入后，一个块的 \(Size\) 会变大，再实现分块的操作时复杂度没有保证

因此需要加入一个操作:当 \(Size_i>2\sqrt n\) 时, \(O(n)\) 重构整个序列，这样每 \(\sqrt n\) 次插入操作会导致一次重构，复杂度为均摊的 \(O(n\sqrt n)\)

然后可以用类似分块的方法来直接维护

\[ \ \]

线段树

静态的操作线段树可以直接维护

在线段树上额外维护一个01，表示这个元素是否出现

将插入操作转化为在让对应位置的0变为1，但是由于不知道插入后的位置，所以不能直接操作

于是有两种解决办法

暴力值域

静态情况下我们对于 \([1,n]\) 建树，但是动态可以对于 \([1,n\cdot q]\) 建函数式线段树

离线

离线维护，预处理出插入的位置

\[ \ \]

平衡树

下面是安利时间

来学Treap吧

它可以

1.查询k大

2.插入元素

3.区间修改

4.区间翻转

5.可持久化!!

6.吊打Splay

Treap 即树堆，意思是在满足二叉查找树的性质同时满足二叉堆的性质

给定每个节点一个额外的随机权值，让二叉查找树对于这个权值满足堆的性质即可

这样构造的二叉查找树，树高是 \(O(\log n)\) 的

带旋Treap

像普通二叉查找树一样每次插入节点到叶子位置后，可能不满足二叉堆的性质，因此需要不断向上zig/zag来调整满足

区间操作可以尝试像写线段树一样写

但是它不可持久化

非旋Treap

维护两个基础操作

1.平衡树合并，操作需要满足两棵树的大小顺序确定，返回新的根

2.平衡树分裂为 \([1,d],[d+1,n]\) 的两部分，返回两棵树的根

1.合并操作 \(x,y\)

按照节点的权值比较谁是平衡树的根，然后将根的左/右子树与另一棵树合并作为新的子树，递归实现

2.分裂 \(x,d\)

维护 \(Size\) 判断是要分裂左子树还是右子树，将子树分裂得到的部分作为 \(x\) 新的子树，递归实现即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef pair <int,int> Pii;
#define mp make_pair
int Union(int x,int y) {
	if(!x || !y) return x|y;
	Down(x),Down(y);
	if(key[x]<key[y]) return rs[x]=Union(rs[x],y),Up(x),x;
	return ls[y]=Union(x,ls[y]),Up(y),y;
}

Pii Split(int x,int d){
	if(!x) return mp(x,x);
	if(sz[x]<=d) return mp(x,0);
	if(d==0) return mp(0,x);
	Down(x);
	if(sz[ls[x]]+1<=d) {
		Pii y=Split(rs[x],d-sz[ls[x]]-1);
		return rs[x]=y.first,Up(x),mp(x,y.second);
	} else {
		Pii y=Split(ls[x],d);
		return ls[x]=y.second,Up(x),mp(y.first,x);
	}
}

插入操作可以分裂前 \(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
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(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)
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;
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;
 
int n,m,cnt;
int head[N],nxt[N],sz[N];
struct Node{ int rk,id; } E[N];
ll s[N],st[N],t[N],d[N],a[N]; 
int ssz[N];
 
ll Get(ll l,ll r){ return (r-l+1)*(l+r)/2; }
void Down(int p) {
    s[p]=0;
    for(int i=head[p];i;i=nxt[i]) {
        if(~st[p]) a[E[i].id]=st[p];
        a[E[i].id]+=1ll*(E[i].rk-1)*d[p]+t[p];
        s[p]+=a[E[i].id];
    }
    st[p]=-1,t[p]=d[p]=0;
}
void Up(int p) {
    s[p]=0;
    for(int i=head[p];i;i=nxt[i]) s[p]+=a[E[i].id];
}
 
void Build() {
    sort(E+1,E+n+1,[&](Node x,Node y){ return x.rk<y.rk; });
    rep(i,0,cnt) sz[i]=head[i]=0,st[i]=-1;
    rep(i,1,n) {
        int p=i/cnt+1;
        nxt[i]=head[p],E[i].rk=++sz[p];
        head[p]=i;
    }
    rep(i,1,cnt) ssz[i]=ssz[i-1]+sz[i],Up(i);
}
 
void Break(){
    rep(i,1,cnt) {
        sz[i]+=sz[i-1],Down(i);
        for(int j=head[i];j;j=nxt[j]) E[j].rk+=sz[i-1];
    }
    Build();
}
 
int Get(int x){
    x--;
    int l=1;
    while(sz[l]<=x) x-=sz[l++];
    return l;
}
 
void Insert(int p,int x){
    int l=p<=n?Get(p):cnt;
    Down(l),p-=ssz[l-1];
    for(int i=head[l];i;i=nxt[i]) if(E[i].rk>=p) E[i].rk++;
    a[++n]=x,E[n]=(Node){p,n},nxt[n]=head[l],head[l]=n;
    sz[l]++,s[l]+=x;
    if(sz[l]>cnt*2.4) Break();
    rep(i,1,cnt) ssz[i]=ssz[i-1]+sz[i];
}
 
void Set(int l,int r,int x) {
    int p1=Get(l),p2=Get(r);
    if(p1==p2) {
        Down(p1);
        for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l && ssz[p1-1]+E[i].rk<=r) a[E[i].id]=x;
        Up(p1);
        return;
    }
    Down(p1),Down(p2);
    s[p1]=s[p2]=0;
    for(int i=head[p1];i;i=nxt[i]) {
        if(ssz[p1-1]+E[i].rk>=l) a[E[i].id]=x;
        s[p1]+=a[E[i].id];
    }
    for(int i=head[p2];i;i=nxt[i]) {
        if(ssz[p2-1]+E[i].rk<=r) a[E[i].id]=x;
        s[p2]+=a[E[i].id];
    }
    rep(i,p1+1,p2-1) st[i]=x,d[i]=t[i]=0,s[i]=1ll*x*sz[i];
}
 
void Add(int l,int r,int x) {
    int p1=Get(l),p2=Get(r);
    if(p1==p2) {
        Down(p1);
        for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l && ssz[p1-1]+E[i].rk<=r) a[E[i].id]+=1ll*(ssz[p1-1]+E[i].rk-l+1)*x;
        Up(p1);
        return;
    }
    Down(p1),Down(p2);
    s[p1]=s[p2]=0;
    for(int i=head[p1];i;i=nxt[i]) {
        if(ssz[p1-1]+E[i].rk>=l) a[E[i].id]+=1ll*(ssz[p1-1]+E[i].rk-l+1)*x;
        s[p1]+=a[E[i].id];
    }
    for(int i=head[p2];i;i=nxt[i]) {
        if(ssz[p2-1]+E[i].rk<=r) a[E[i].id]+=1ll*(ssz[p2-1]+E[i].rk-l+1)*x;
        s[p2]+=a[E[i].id];
    }
    rep(i,p1+1,p2-1) {
        t[i]+=1ll*(ssz[i-1]-l+2)*x,d[i]+=x;
        s[i]+=Get(ssz[i-1]-l+2,ssz[i]-l+1)*x;
    }
}
 
ll Que(int l,int r) {
    int p1=Get(l),p2=Get(r);
    ll ans=0;
    Down(p1),Down(p2);
    if(p1==p2) {
        Down(p1);
        for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l && ssz[p1-1]+E[i].rk<=r) ans+=a[E[i].id];
        return ans;
    }
    Down(p1),Down(p2);
    for(int i=head[p1];i;i=nxt[i]) if(ssz[p1-1]+E[i].rk>=l) ans+=a[E[i].id];
    for(int i=head[p2];i;i=nxt[i]) if(ssz[p2-1]+E[i].rk<=r) ans+=a[E[i].id];
    rep(i,p1+1,p2-1) ans+=s[i];
    return ans;
}
 
int main(){
    n=rd(),m=rd();
    cnt=ceil(sqrt(n+m));
    rep(i,1,n) a[i]=rd(),E[i]=(Node){i,i};
    Build();
    rep(i,1,m) {
        int opt=rd();
        if(opt==1) {
            int l=rd(),r=rd(),x=rd();
            Set(l,r,x);
        } else if(opt==2) {
            int l=rd(),r=rd(),x=rd();
            Add(l,r,x);
        } else if(opt==3) {
            int p=rd(),x=rd();
            Insert(p,x);
        } else if(opt==4) {
            int l=rd(),r=rd();
            printf("%lld\n",Que(l,r));
        }
    }
}

旋Treap:

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
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> Pii;
#define reg register
#define pb push_back
#define mp make_pair
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(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)
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;
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;

int n;
int rt,son[N][2],fa[N];
ll s[N],t[N],d[N],st[N],val[N];
ll sz[N],key[N];

void Up(int p) {
	s[p]=s[son[p][0]]+s[son[p][1]]+val[p];
	sz[p]=sz[son[p][0]]+sz[son[p][1]]+1;
}
void Set(int p,ll x){
	t[p]=d[p]=0,st[p]=val[p]=x,s[p]=sz[p]*x;
}
void Add(int p,ll x,ll d) {
	val[p]+=x+d*sz[son[p][0]];
	s[p]+=sz[p]*(sz[p]-1)/2*d+x*sz[p];
	t[p]+=x,::d[p]+=d;
}
void Down(int p) {
	if(~st[p]) Set(son[p][0],st[p]),Set(son[p][1],st[p]),st[p]=-1;
	if(t[p] || d[p]) Add(son[p][0],t[p],d[p]),Add(son[p][1],t[p]+(sz[son[p][0]]+1)*d[p],d[p]),t[p]=d[p]=0;
}

void rotate(int u) {
	int f=fa[u],ff=fa[f],d=son[f][1]==u;
	fa[u]=ff; if(ff) son[ff][son[ff][1]==f]=u;
	son[f][d]=son[u][!d]; if(son[u][!d]) fa[son[u][!d]]=f;
	son[u][!d]=f,fa[f]=u;
	Up(f),Up(u);
}

void Insert(int p,int x){
	int v=++n;
	val[v]=s[v]=x,sz[v]=1,st[v]=-1,key[v]=rand();
	if(!rt){ rt=v; return; }
	int u=rt;
	while(u) {
		Down(u);
		if(sz[son[u][0]]>=p) {
			if(!son[u][0]) { son[fa[v]=u][0]=v; break; }
			u=son[u][0]; 
		} else {
			p-=sz[son[u][0]]+1;
			if(!son[u][1]) { son[fa[v]=u][1]=v; break; }
			u=son[u][1];
		}
	}
	while(fa[v] && key[v]<key[fa[v]]) rotate(v);
	if(!fa[v]) rt=v;
	while(fa[v]) Up(v=fa[v]);
}

void Set(int p,int l,int r,int x) {
	if(!p || r<=0 || l>sz[p]) return;
	if(l<=1 && r>=sz[p]) return Set(p,x);
	int t=sz[son[p][0]]+1;
	Down(p),Set(son[p][0],l,r,x),Set(son[p][1],l-t,r-t,x);
	if(t>=l && t<=r) val[p]=x;
	Up(p);
}

void Add(int p,int l,int r,ll x,ll d) {
	if(!p || r<=0 || l>sz[p]) return;
	if(l<=1 && r>=sz[p]) return Add(p,x,d);
	int t=sz[son[p][0]]+1;
	Down(p),Add(son[p][0],l,r,x,d),Add(son[p][1],l-t,r-t,x+d*t,d);
	if(t>=l && t<=r) val[p]+=(t-1)*d+x;
	Up(p);
}

ll Que(int p,int l,int r) {
	if(!p || r<=0 || l>sz[p]) return 0;
	if(l<=1 && r>=sz[p]) return s[p];
	ll t=sz[son[p][0]]+1,res=0;
	Down(p),res+=Que(son[p][0],l,r),res+=Que(son[p][1],l-t,r-t);
	if(t>=l && t<=r) res+=val[p];
	return res;
}

int main(){
	int n=rd(),m=rd();
	rep(i,0,n-1) Insert(i,rd());
	while(m--) {
		int opt=rd();
		if(opt==1) {
			int l=rd(),r=rd();
			Set(rt,l,r,rd());
		} else if(opt==2) {
			int l=rd(),r=rd(),x=rd();
			Add(rt,l,r,x-1ll*(l-1)*x,x);
		} else if(opt==3) {
			int x=rd(),y=rd();
			Insert(x-1,y);
		} else {
			int l=rd(),r=rd();
			printf("%lld\n",Que(rt,l,r));
		}
	}
}



非旋Treap:

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> Pii;
#define mp make_pair
int rd(){
    char c;int s=0;
    while((c=getchar())<48);
    do s=s*10+c-48;
    while((c=getchar())>47);
    return s;
}
enum{N=200010};
int n,m,rt,ls[N],rs[N],key[N];
ll s[N],t[N],d[N],st[N],val[N],sz[N];
 
inline void Up(int p) {
    s[p]=s[ls[p]]+s[rs[p]]+val[p];
    sz[p]=sz[ls[p]]+sz[rs[p]]+1;
}
inline void Set(int p,ll x){ t[p]=d[p]=0,st[p]=val[p]=x,s[p]=sz[p]*x; }
inline void Add(int p,ll x,ll d) {
    val[p]+=x+d*sz[ls[p]];
    s[p]+=sz[p]*(sz[p]-1)/2*d+x*sz[p];
    t[p]+=x,::d[p]+=d;
}
inline void Down(int p) {
    ~st[p] && (Set(ls[p],st[p]),Set(rs[p],st[p]),st[p]=-1);
    (t[p] || d[p]) && (Add(ls[p],t[p],d[p]),Add(rs[p],t[p]+(sz[ls[p]]+1)*d[p],d[p]),t[p]=d[p]=0);
}
int Union(int x,int y) {
    if(!x || !y) return x|y;
    return key[x]<key[y]?(Down(x),rs[x]=Union(rs[x],y),Up(x),x):(Down(y),ls[y]=Union(x,ls[y]),Up(y),y);
}
Pii Split(int x,int d){
    if(sz[x]<=d) return mp(x,0);
    if(d==0) return mp(0,x);
    Down(x);
    if(sz[ls[x]]+1<=d) {
        Pii y=Split(rs[x],d-sz[ls[x]]-1);
        return rs[x]=y.first,Up(x),mp(x,y.second);
    } else {
        Pii y=Split(ls[x],d);
        return ls[x]=y.second,Up(x),mp(y.first,x);
    }
}
 
int main(){
    n=rd(),m=rd();
    for(int i=1;i<=n+m;++i) key[i]=rand(),st[i]=-1,sz[i]=1;
    for(int i=1;i<=n;++i) val[i]=s[i]=rd(),rt=Union(rt,i);
    while(m--){
        int opt=rd();
        if(opt==3) {
            Pii t=Split(rt,rd()-1); ++n,val[n]=s[n]=rd();
            rt=Union(Union(t.first,n),t.second);
        } else {
            int l=rd(),r=rd();
            Pii a=Split(rt,l-1),b=Split(a.second,r-l+1);
            if(opt==1) Set(b.first,rd());
            else if(opt==2) {int x=rd(); Add(b.first,x,x); }
            else if(opt==4) printf("%lld\n",s[b.first]);
            rt=Union(Union(a.first,b.first),b.second);
        }
    }
}

Posted on Edited on In

美丽的桥梁

可以得到一个Naive的暴力方法来判断在 \((L,R)\) 上修桥是否合法:

显然的性质: 如果有相交，则一定存在一个关键点相交

设得到的圆半径为 \(r=\frac{x_R-x_L}{2}\) ，圆心为 \((x,y)=(\frac{x_L+x_R}{2},h-r)\)

枚举每个 \(i\in [L,R]\) 判断是否点 \(x_i,y_i\) 是否相交，如果相交，只需要满足

\(y_i>y\) ，且 其与圆心距离 \(>r\)

\[ \ \]

考虑优化判断，将生成的拱形分为左右两部分，分别考虑即可

推论: 对于每个 \(L\) ，其左半边不相交的半径为描述为一个范围 \([0,A_L]\)

同理的，对于每个 \(R\) 也是如此，能求得一个范围 \([0,B_R]\)

考虑对于每个 \(L\) ，枚举每个 \(i>L\) 来求出 \(A_L\)

设半径为 \(r\) ，列出圆心与点 \(x_i,y_i\) 距离的表达式，必须满足距离 \(\leq r\) ，就能得到一个二次方程

二次方程的解集为 \(x_1,x_2\) ，但是实际上 \([0,x_1]\) 这一段不满足 \(y_i>y\) ，因此也是合法的

即将每次求得的 \([0,x_2]\) 区间取交集即可

复杂度为 \(O(n^2)\)

同理求得每个 \(B_R\)

考虑朴素的dp，令 \(dp_i\) 表示解决了 \([1,i]\) 前缀的最小代价

枚举 \(j\) ， \(O(1)\) 判断 \((i,j)\) 是否合法，然后进行转移

tips: 题目的代价计算方法可能没讲清楚。。。

复杂度为 \(O(n^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
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
typedef double db;
typedef long long ll;
#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,const T &b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,const T &b){ ((a<b)&&(a=b)); }

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=1e4+10;
const db eps=1e-9;
const ll INF=4e18;

int n,h,a,b;
int X[N],Y[N];
db L[N],R[N];
db Sqr(db x){ return x*x; }
ll dp[N];

int main(){
	n=rd(),h=rd(),a=rd(),b=rd();
	rep(i,1,n) X[i]=rd(),Y[i]=rd();
	rep(i,1,n) {
		L[i]=min((db)(X[n]-X[i])/2,(db)(h-Y[i]));
		rep(j,i+1,n) {
			if(X[j]-X[i]>L[i]+eps) break;
			db a=1,b=2*(X[i]-X[j]+Y[j]-h),c=Sqr(X[i]-X[j])+Sqr(Y[j]-h);
			db d=sqrt(b*b-4*a*c);
			db r=(-b+d)/(2*a);
			cmin(L[i],r);
		}
		L[i]*=2;
	}
	rep(i,1,n) {
		R[i]=min((db)(X[i]-X[1])/2,(db)(h-Y[i]));
		drep(j,i-1,1) {
			if(X[i]-X[j]>R[i]+eps) break;
			db a=1,b=2*(X[j]-X[i]+Y[j]-h),c=Sqr(X[j]-X[i])+Sqr(Y[j]-h);
			db d=sqrt(b*b-4*a*c);
			db r=(-b+d)/(2*a);
			cmin(R[i],r);
		}
		R[i]*=2;
	}
	dp[1]=1ll*a*(h-Y[1]);
	rep(i,2,n) {
		dp[i]=INF;
		drep(j,i-1,1) {
			if(X[i]-X[j]>R[i]+eps) break;
			if(X[i]-X[j]>L[j]+eps) continue;
			cmin(dp[i],dp[j]+1ll*a*(h-Y[i])+1ll*(X[i]-X[j])*(X[i]-X[j])*b);
		}
	}
	if(dp[n]<INF) printf("%lld\n",dp[n]);
	else puts("impossible");
}

0%