GGAutomaton's Blog
0%

发表于 分类于 ，

边分治最怕菊花图
所以要对原图进行改造

https://blog.csdn.net/make_it_for_good/article/details/52194466

需要用vector存储邻接表
方法妙不可言
0边是虚边，1边是实边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int x=1;x<=n;x++) {   
       int t=a[x].size();
       if(t==0)continue;
       if(t==1) {
           add(x,a[x][0],1);add(a[x][0],x,1);
           continue;
       }
       for(int i=2;i<t<<1;i<<=1)
           for(int j=0;j<t;j+=i) {
               add(++n,a[x][j],i==2 ? 1:0);
               add(a[x][j],n,i==2 ? 1:0);
               a[x][j]=n;v[n]=v[x];
               if(j+(i>>1)<t) {   
                   add(n,a[x][j+(i>>1)],i==2 ? 1:0);
                   add(a[x][j+(i>>1)],n,i==2 ? 1:0);
               }
           }
       add(n,x,0);add(x,n,0);
   }

发表于 分类于 ，

给定一棵n个点的树,每条边有权值。
求一条链，这条链包含的边数在L和U之间，且平均边权最大。

类似于分数规划问题，转换为二分答案
将每条边减去二分值，判断是否有权值和大于等于0的链
处理出根到其中一个子树中每种深度的最大权值和
另外记录一下根到已知子树中每种深度的最大权值和
就变成了定区间求最值，用单调队列即可

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
#include<iostream>
#include<cstdio>
using namespace std;
int head[100005],vet[200005],nxt[200005],w[200005],num;
bool vis[100005];
int sz[100005],mxs[100005],root,sz1,sz2;
int que[100005];
double mxr,ans,mid,d1[100005],d2[100005];
int L,U,n;
inline int read() {
    char ch=0;int sum=0;
    while (ch>'9'||ch<'0') ch=getchar();
    while (ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
    return sum;
}
inline void addedge(int x,int y,int c) {
    num++;vet[num]=y;nxt[num]=head[x];w[num]=c;head[x]=num;
    num++;vet[num]=x;nxt[num]=head[y];w[num]=c;head[y]=num;
}
void getdepth(int x,int ff,int dep,double sum) {
    if (dep>sz2) {
        sz2=dep;
        d2[dep]=-1e11;
    }
    d2[dep]=max(d2[dep],sum);
    for (int e=head[x];e;e=nxt[e]) {
        if (vet[e]==ff||vis[vet[e]]) continue;
        getdepth(vet[e],x,dep+1,sum+w[e]-mid);
    }
}
inline double calc() {
    int h=1,t=0;
    int i=min(U,sz2),j=0;
    double mx=-1e11;
    for (;i;i--) {
        while (j<=sz1&&i+j<=U) {
            while (h<=t&&d1[que[t]]<=d1[j]) t--;
            que[++t]=j;
            j++;
        }
        while (h<=t&&que[h]+i<L) h++;
        if (h>t) return mx;
        mx=max(mx,d1[que[h]]+d2[i]);
        if (mx>=0) return mx;
    }
    return mx;
}
inline bool check(int x) {
    sz1=sz2=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (vis[v]) continue;
        getdepth(v,x,1,w[e]-mid);
        if (calc()>=0) return true;
        for (int i=1;i<=sz2;i++) {
            if (i>sz1) d1[i]=-1e11;
            d1[i]=max(d1[i],d2[i]);
            d2[i]=-1e11;
        }
        sz1=max(sz1,sz2);
        sz2=0;
    }
    return false;
}
void bs(int x) {
    double l=ans,r=mxr;
    while (r-l>=0.0001) {
        mid=(l+r)/2;
        if (check(x)) l=mid;
        else r=mid;
    }
    ans=max(ans,l);
}
void getroot(int x,int ff,int tt) {
    sz[x]=1;mxs[x]=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (vis[v]||v==ff) continue;
        getroot(v,x,tt);
        sz[x]+=sz[v];
        mxs[x]=max(mxs[x],sz[v]);
    }
    mxs[x]=max(mxs[x],tt-sz[x]);
    if (mxs[root]>mxs[x]) root=x;
}
void solve(int x,int tot) {
    bs(x);
    vis[x]=1;
    for (int e=head[x];e;e=nxt[e]) {
        if (vis[vet[e]]) continue;
        int tt=sz[vet[e]];root=0;
        if (tt>sz[x]) tt=tot-sz[x];
        getroot(vet[e],x,tt);
        solve(root,tt);
    }
}
int main() {
    n=read();L=read();U=read();
    for (int i=1;i<n;i++) {
        int x=read(),y=read(),c=read();
        addedge(x,y,c);
        mxr=max(mxr,(double)c);
    }
    for (int i=1;i<=n;i++) d1[i]=d2[i]=-1e11;
    mxs[0]=1e9;
    getroot(1,0,n);
    solve(root,n);
    printf("%.3lf",ans);
    return 0;
}

蒟蒻用dfs算距离
dalao用bfs算距离
http://hzwer.com/5362.html
蒟蒻的常数肯定比dalao大 orz

发表于 分类于 ，

模板题：https://www.luogu.org/problemnew/show/P3806

给定一棵有n个点的树，m次询问树上距离为k的点对是否存在。k很大，m较小。

1.暴力做法，可能变成n^2 （756ms） 

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
#include<iostream>
#include<cstdio>
using namespace std;
const int maxK=10000001;
int head[10005],vet[20005],nxt[20005],w[20005],num;
int sz[10005],mxs[10005],root;
int d[10005],top,found[10000005];
bool vis[10005];
int n,m;
void addedge(int x,int y,int c) {
    num++;vet[num]=y;nxt[num]=head[x];w[num]=c;head[x]=num;
    num++;vet[num]=x;nxt[num]=head[y];w[num]=c;head[y]=num;
}
void getroot(int x,int ff,int tt) {
    sz[x]=1;mxs[x]=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (v==ff || vis[v]) continue;
        getroot(v,x,tt);
        sz[x]+=sz[v];
        mxs[x]=max(mxs[x],sz[v]);
    }
    mxs[x]=max(mxs[x],tt-sz[x]);
    if (mxs[x]<mxs[root]) root=x;
}
void getdepth(int x,int ff,int depth) {
    d[++top]=depth;
    for (int e=head[x];e;e=nxt[e]) {
        if (vet[e]==ff || vis[vet[e]]) continue;
        getdepth(vet[e],x,depth+w[e]);
    }
}
void cal(int x,int typ,int val) {
    top=0;
    getdepth(x,0,0);
    for (int i=1;i<=top;i++)
        for (int j=1;j<=top;j++) {
            if (typ && d[i]+d[j]<=maxK) found[d[i]+d[j]]++;
            else if (d[i]+d[j]+val<=maxK) found[d[i]+d[j]+val]--;
        }
}
void solve(int x,int tot) {
    cal(x,1,0);
    vis[x]=true;
    for (int e=head[x];e;e=nxt[e]) {
        if (!vis[vet[e]]) {
            cal(vet[e],0,w[e]*2);//刷答案的地方视具体题目而定
            root=0;
            int tt=sz[vet[e]];
            if (tt>sz[x]) tt=tot-sz[x];//主流写法没有这一句。这样写保证不退化，运行速度略微提升。
            getroot(vet[e],x,tt);
            solve(root,tt);
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<n;i++) {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        addedge(x,y,c);
    }
    mxs[0]=(n<<1);root=0;
    getroot(1,0,n);
    solve(root,n);
    while (m--) {
        int x;
        scanf("%d",&x);
        if (found[x]) printf("AYE\n");
        else printf("NAY\n");
    }
    return 0;
}

其实嘛
我觉得常规写法子树的总节点数tot有问题
如果子树是上一次root的父亲
size[to]是不能直接用的，需要-size[oldroot]
实验证明主流解法的确分得不太均匀
不过因为众多子树中只有一个会出错，问题也不大

另附主流写法核心代码

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
void getroot(int x,int ff) {
    sz[x]=1;mxs[x]=0;
    for (int e=head[x];e;e=nxt[e]) {
        int v=vet[e];
        if (v==ff || vis[v]) continue;
        getroot(v,x);
        sz[x]+=sz[v];
        mxs[x]=max(mxs[x],sz[v]);
    }
    mxs[x]=max(mxs[x],tt-sz[x]);
    if (mxs[x]<mxs[root]) root=x;
}
void solve(int x) {
    cal(x,1,0);
    vis[x]=true;
    for (int e=head[x];e;e=nxt[e]) {
        if (!vis[vet[e]]) {
            cal(vet[e],0,w[e]*2);
            root=0;
            tt=sz[vet[e]];//?
            getroot(vet[e],x);
            solve(root);
        }
    }
}

2.优化，枚举询问 （16ms） 

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
#include<iostream>
#include<cstdio>
using namespace std;
const int maxK=10000001;
int head[10005],vet[20005],nxt[20005],w[20005],num;
int sz[10005],mxs[10005],root;
int d[10005],q[105],xg[10005];
bool vis[10005],found[10000005],ans[105];
int n,m;
inline int read() {
	char ch=0;int sum=0;
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') sum=sum*10+ch-'0',ch=getchar();
	return sum;
}
inline void addedge(int x,int y,int c) {
	num++;vet[num]=y;nxt[num]=head[x];w[num]=c;head[x]=num;
	num++;vet[num]=x;nxt[num]=head[y];w[num]=c;head[y]=num;
}
void getroot(int x,int ff,int tt) {
	sz[x]=1;mxs[x]=0;
	for (int e=head[x];e;e=nxt[e]) {
		int v=vet[e];
		if (v==ff || vis[v]) continue;
		getroot(v,x,tt);
		sz[x]+=sz[v];
		mxs[x]=max(mxs[x],sz[v]);
	}
	mxs[x]=max(mxs[x],tt-sz[x]);
	if (mxs[x]<mxs[root]) root=x;
}
void getdepth(int x,int ff,int depth) {
    d[++d[0]]=depth;
	for (int e=head[x];e;e=nxt[e]) {
		if (vet[e]==ff || vis[vet[e]]) continue;
		getdepth(vet[e],x,depth+w[e]);
	}
}
inline void calc(int x,int val) {
	d[0]=0;
	getdepth(x,0,val);
	for (int i=1;i<=d[0];i++)
		for (int j=1;j<=m;j++) 
			if (q[j]>=d[i]) ans[j]|=found[q[j]-d[i]];
	for (int i=1;i<=d[0];i++) found[d[i]]=1,xg[++xg[0]]=d[i];
}
void solve(int x,int tot) {
	vis[x]=true;xg[0]=0;found[0]=1;
	for (int e=head[x];e;e=nxt[e]) {
		if (!vis[vet[e]]) calc(vet[e],w[e]);
	}
	for (int i=1;i<=xg[0];i++) found[xg[i]]=0;
	for (int e=head[x];e;e=nxt[e]) {
		if (!vis[vet[e]]) {
			root=0;
			int tt=sz[vet[e]];
			if (tt>sz[x]) tt=tot-sz[x];
			getroot(vet[e],x,tt);
			solve(root,tt);
		}
	}
}
int main() {
	n=read();m=read();
	for (int i=1;i<n;i++) {
		int x=read(),y=read(),c=read();
		addedge(x,y,c);
	}
	for (int i=1;i<=m;i++) q[i]=read();
	mxs[0]=(n<<1);root=0;
	getroot(1,0,n);
	solve(root,n);
	for (int i=1;i<=m;i++) {
		if (ans[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}

发表于 分类于 ，

P3834 【模板】可持久化线段树 1（主席树）
查询区间[l,r]内的第k小值

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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[200005],ls[200005],nn;
int root[200005];
int sum[4322005],lson[4322005],rson[4322005],num;
int n,m;
inline int read() {
    char ch=0;int sum=0,fu=1;
    while ((ch>'9'||ch<'0')&&(ch!='-')) ch=getchar();
    if (ch=='-') fu=-1,ch=getchar();
    while (ch<='9'&&ch>='0') sum=sum*10+ch-'0',ch=getchar();
    return fu*sum;
}
void build(int &k,int l,int r) {
    k=++num;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(lson[k],l,mid);
    build(rson[k],mid+1,r);
}
void update(int oldp,int &newp,int l,int r,int ll) {
    newp=++num;
    if (l==ll && l==r) {
        sum[newp]=sum[oldp]+1;
        return;
    }
    int mid=(l+r)>>1;
    lson[newp]=lson[oldp];rson[newp]=rson[oldp];
    if (mid>=ll) update(lson[oldp],lson[newp],l,mid,ll);
    else update(rson[oldp],rson[newp],mid+1,r,ll);
    sum[newp]=sum[lson[newp]]+sum[rson[newp]];
}
int query(int p1,int p2,int l,int r,int k) {
    if (l==r) return l;
    int mid=(l+r)>>1,tmp=sum[lson[p2]]-sum[lson[p1]];
    if (tmp>=k) return query(lson[p1],lson[p2],l,mid,k);
    else return query(rson[p1],rson[p2],mid+1,r,k-tmp);
}
int main() {
    n=read();m=read();
    for (int i=1;i<=n;i++) ls[i]=a[i]=read();
    sort(ls+1,ls+n+1);
    nn=unique(ls+1,ls+n+1)-ls-1;
    build(root[0],1,n);
    for (int i=1;i<=n;i++) {
        int po=lower_bound(ls+1,ls+nn+1,a[i])-ls;
        update(root[i-1],root[i],1,n,po);
    }
    while (m--) {
        int x=read(),y=read(),k=read();
        printf("%d\n",ls[query(root[x-1],root[y],1,n,k)]);
    }
    return 0;
}

发表于 分类于 ，

一、扩展欧几里得

二、欧拉定理

三、线性求逆

原理：http://blog.miskcoo.com/2014/09/linear-find-all-invert

四、代码汇总

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
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
int num,P,gcd;
LL A[3000005]; 
void exgcd(int a,int b,int &x,int &y) {
    if(b==0) {gcd=a;x=1;y=0;}
    else {exgcd(b,a%b,y,x);y-=x*(a/b);}
}
LL fast_pow(LL B, LL x) {
    LL tmp=1;
    while (x>0) {
        if (x&1) tmp=tmp*B%P;
        B=B*B%P;
        x>>=1;
    }
    return tmp;
}
int main() {
	cin >> num >> P;
	
	int x,y;
	exgcd(num,P,x,y);
	printf("%d\n",(x%P+P)%P);
	
	printf("%d\n",fast_pow(num,P-2));
	
	A[1]=1;printf("%d\n",A[1]);
    for(int i=2;i<=num;i++) {
        A[i]=(P-(P/i))*A[P%i]%P;
		printf("%d\n",A[i]);
    }
	return 0;
}

发表于 分类于 ，

原理：http://www.cnblogs.com/zwfymqz/p/8094500.html
模板题：https://www.luogu.org/problemnew/show/P3384
操作1： 格式： 1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z
操作2： 格式： 2 x y 表示求树从x到y结点最短路径上所有节点的值之和
操作3： 格式： 3 x z 表示将以x为根节点的子树内所有节点值都加上z
操作4： 格式： 4 x 表示求以x为根节点的子树内所有节点值之和

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
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;
int head[100005],vet[200005],nxt[200005],num;
int fa[100005],son[100005],sz[100005];//son是重儿子
int depth[100005],top[100005];//均为原编号，top是x所在重链的顶点
int idx[100005],cnt;//idx是x的新编号
int a[100005],b[100005];//a是原编号的值，val是新编号的值
LL sum[400005],tag[400005];//均为新编号
int n,m,root,P;
inline void addedge(int x,int y) {
	num++;vet[num]=y;nxt[num]=head[x];head[x]=num;
	num++;vet[num]=x;nxt[num]=head[y];head[y]=num;
} 
void dfs1(int x,int ff,int dep) {
	depth[x]=dep;fa[x]=ff;sz[x]=1;
	int mx=0;
	for (int e=head[x];e;e=nxt[e]) {
		int v=vet[e];
		if (ff==v) continue;
		dfs1(v,x,dep+1);
		sz[x]+=sz[v];
		if (sz[v]>mx) mx=sz[v],son[x]=v;
	}
}
void dfs2(int x,int tp) {
	idx[x]=++cnt;
	b[cnt]=a[x]%P;
	top[x]=tp;
	if (!son[x]) return;//别忘了这句
	dfs2(son[x],tp);
	for (int e=head[x];e;e=nxt[e])
		if (!idx[vet[e]]) dfs2(vet[e],vet[e]);
}
void build(int l,int r,int pp) {
	if (l==r) {
		sum[pp]=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,pp<<1);
	build(mid+1,r,pp<<1|1);
	sum[pp]=(sum[pp<<1]+sum[pp<<1|1])%P;
}
inline void pushdown(int l,int r,int pp) {
	if (!tag[pp]) return;
	if (l==r) {tag[pp]=0;return;}
	int mid=(l+r)>>1;
	sum[pp<<1]=(sum[pp<<1]+tag[pp]*(mid-l+1))%P;
	tag[pp<<1]=(tag[pp<<1]+tag[pp])%P;
	sum[pp<<1|1]=(sum[pp<<1|1]+tag[pp]*(r-mid))%P;
	tag[pp<<1|1]=(tag[pp<<1|1]+tag[pp])%P;
	tag[pp]=0;
}
LL query(int l,int r,int pp,int ll,int rr) {
	if (l==ll && r==rr) return sum[pp];
	pushdown(l,r,pp);
	int mid=(l+r)>>1;
	if (mid>=rr) return query(l,mid,pp<<1,ll,rr);
	else if (mid<ll) return query(mid+1,r,pp<<1|1,ll,rr);
	else return (query(l,mid,pp<<1,ll,mid)+query(mid+1,r,pp<<1|1,mid+1,rr))%P;
}
void update(int l,int r,int pp,int ll,int rr,int v) {
	if (l==ll && r==rr) {
		sum[pp]=(sum[pp]+(LL)(r-l+1)*v)%P;
		tag[pp]=(tag[pp]+v)%P;
		return;
	}
	pushdown(l,r,pp);
	int mid=(l+r)>>1;
	if (mid>=rr) update(l,mid,pp<<1,ll,rr,v);
	else if (mid<ll) update(mid+1,r,pp<<1|1,ll,rr,v);
	else update(l,mid,pp<<1,ll,mid,v),update(mid+1,r,pp<<1|1,mid+1,rr,v);
	sum[pp]=(sum[pp<<1]+sum[pp<<1|1])%P;
}
inline LL pathsum(int x,int y) {
	LL ans=0;
	while (top[x]!=top[y]) {
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		ans=(ans+query(1,n,1,idx[top[x]],idx[x]))%P;
		x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	ans=(ans+query(1,n,1,idx[x],idx[y]))%P;
	return ans;
}
inline void pathadd(int x,int y,int v) {
	while (top[x]!=top[y]) {
		if (depth[top[x]]<depth[top[y]]) swap(x,y);
		update(1,n,1,idx[top[x]],idx[x],v);
		x=fa[top[x]];
	}
	if (depth[x]>depth[y]) swap(x,y);
	update(1,n,1,idx[x],idx[y],v);
}
int main() {
	cin >> n >> m >> root >> P;
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<n;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		addedge(x,y);
	}
	dfs1(root,0,1);
	dfs2(root,root);
	build(1,n,1);
	while (m--) {
		int op,x,y,z;
		scanf("%d",&op);
		if (op==1) {
			scanf("%d%d%d",&x,&y,&z);
			pathadd(x,y,z);
		}
		if (op==2) {
			scanf("%d%d",&x,&y);
			printf("%lld\n",pathsum(x,y));
		}
		if (op==3) {
			scanf("%d%d",&x,&z);
			update(1,n,1,idx[x],idx[x]+sz[x]-1,z%P);
		}
		if (op==4) {
			scanf("%d",&x);
			printf("%lld\n",query(1,n,1,idx[x],idx[x]+sz[x]-1));
		}
	}
	return 0;
}

据说n特别大的时候，需要使用bfs防爆栈

发表于 分类于 ，

从多项式乘法到快速傅里叶变换，Miskcoo
FFT 学习笔记，Menci

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
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=2100000;//两倍空间
const double pi=acos(-1);
struct complex_t {
	double a,b;
	complex_t operator *(const complex_t &res) {
		return (complex_t){a*res.a-b*res.b,a*res.b+b*res.a};
	}
	complex_t operator +(const complex_t &res) {
		return (complex_t){a+res.a,b+res.b};
	}
	complex_t operator -(const complex_t &res) {
		return (complex_t){a-res.a,b-res.b};
	}
	void operator *=(const complex_t &res) {
		*this=(*this)*res;
	}
	void operator +=(const complex_t &res) {
		*this=(*this)+res;
	}
};
int n,m,step,r[MAXN];
complex_t a[MAXN],b[MAXN];
inline int read() {
	char ch=getchar();int sum=0;
	while (ch>'9' || ch<'0') ch=getchar();
	while (ch>='0' && ch<='9') sum=sum*10+ch-'0',ch=getchar();
	return sum;
}
void DFT(complex_t c[],int T) {//1:DFT -1:IDFT
	for (int i=0;i<n;i++) {
		if (i<r[i]) swap(c[i],c[r[i]]);
	}
	for (int i=1;i<n;i<<=1) {
		complex_t x=(complex_t){cos(pi/i),T*sin(pi/i)};
		for (int j=0;j<n;j+=(i<<1)) {
			complex_t y=(complex_t){1,0};
			for (int k=0;k<i;k++,y=y*x) {
				complex_t z=y*c[i+j+k];
				c[i+j+k]=c[j+k]-z;
				c[j+k]+=z;//顺序不可颠倒 
			}
		}
	}
}
void FFT() {
	m+=n;n=1;//n+m次多项式，n+m+1项 
	while (n<=m) n<<=1,step++;//必须>n+m，n=(1<<step) 
	for (int i=0;i<n;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(step-1));//计算元素最终的位置 
	DFT(a,1);DFT(b,1);//DFT
	for (int i=0;i<=n;i++) a[i]*=b[i];
	DFT(a,-1);//IDFT
	for (int i=0;i<=m;i++) a[i].a=a[i].a/n+0.5;//IDFT 1/n
}
int main() {
	n=read(),m=read();//n次多项式，n+1个项 
	for (int i=0;i<=n;i++) a[i].a=read();
	for (int i=0;i<=m;i++) b[i].a=read();
	FFT();
	for (int i=0;i<=m;i++) printf("%d ",(int)a[i].a);
	return 0;
}

发表于 分类于 ，

r[i]是处理后每个字符的回文半径
r[i]-1即为处理前回文子串长度
P3805 【模板】manacher算法

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
#include<iostream>
#include<cstdio>
using namespace std;
const int P=19930726;
typedef long long LL;
char str[2000005];
int r[2000005],a[1000005];
LL sum[1000005];
int n,len;
LL k,ans=1;
void fast_pow(LL base,LL x) {
	base%=P;
	while (x>0) {
		if (x&1) ans=ans*base%P;
		base=base*base%P;
		x>>=1;
	}
}
void read() {
	char ch;
	len=1;str[1]='#';
	while (ch<'a'||ch>'z') ch=getchar();
	while (ch<='z'&&ch>='a') {
		str[++len]=ch;
		str[++len]='#';//避免奇偶性讨论
		ch=getchar();
	}
	str[0]='$';str[len+1]='@';//防止下标越界
}
void manacher() {
	int p=0,mx=0;
	for (int i=1;i<=len;i++) {
		if (mx>i) r[i]=min(r[2*p-i],mx-i);
		else r[i]=1;
		while (str[i+r[i]]==str[i-r[i]]) r[i]++;
		if (i+r[i]>mx) p=i,mx=i+r[i];
	}
}
int main() {
	scanf("%d%lld",&n,&k);
	read();
	manacher();
	for (int i=2;i<len;i+=2) a[1]++,a[r[i]]--;
	for (int i=1;i<=(len>>1);i++) sum[i]=sum[i-1]+a[i];
	if (!(n&1)) n--;
	for (int i=n;i>0;i-=2) {
		if (!sum[i]) continue;
		LL tmp=min(k,sum[i]);
		fast_pow(i,tmp);
		k-=tmp;
		if (k<=0) break;
	}
	if (k>0) cout<<-1;
	else printf("%lld",ans);
	return 0;
}

发表于 分类于 ，

https://www.luogu.org/problemnew/show/P4146

3种操作：
1.将[L,R]这个区间内的所有数加上V。
2.将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。
3.求[L,R]这个区间中的最大值。

由于交换两个子树必定会改变BST的性质
所以不能用key值做find
只能用size表示数组元素下标
查询下标为k的元素用find_Kth

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm> //for swap();
using namespace std;
int fa[50005],ch[50005][2],size[50005];
bool reversed[50005];
int tag[50005],mx[50005],val[50005];//特别注意0点初始化的值，而且所有操作不能修改它
int num,root;
int n,m;
inline void update(int x) {
	int lson=ch[x][0],rson=ch[x][1];
    size[x]=size[lson]+size[rson]+1;
    mx[x]=max(val[x],max(mx[lson],mx[rson]));
}
inline void pushdown(int x) {
	if (reversed[x]) {
		if (ch[x][0]) reversed[ch[x][0]]^=1;
		if (ch[x][1]) reversed[ch[x][1]]^=1;
		swap(ch[x][0],ch[x][1]);//#include<algorithm>
		reversed[x]=0;
	}
	if (tag[x]) {
		int lson=ch[x][0],rson=ch[x][1];
		if (lson) {
			tag[lson]+=tag[x];
			val[lson]+=tag[x];
			mx[lson]+=tag[x];
		}
		if (rson) {
			tag[rson]+=tag[x];
			val[rson]+=tag[x];
			mx[rson]+=tag[x];
		}
		tag[x]=0;
	}
}
inline void rotate(int x) {
	int fa1=fa[x],fa2=fa[fa1],side=(ch[fa[x]][1]==x);
	pushdown(fa1);pushdown(x);
	ch[fa1][side]=ch[x][side^1];fa[ch[fa1][side]]=fa1;
	fa[fa1]=x;ch[x][side^1]=fa1;
	fa[x]=fa2;
	if (fa2) ch[fa2][ch[fa2][1]==fa1]=x;
	update(fa1);update(x);
}
inline void splay(int x,int goal) {//由于Kth里面做了pushdown，这里可以不做
    while (fa[x]!=goal) {
        int fa1=fa[x],fa2=fa[fa1];
        if (fa2!=goal) {
			if ((ch[fa2][0]==fa1)^(ch[fa1][0]==x)) rotate(x);
			else rotate(fa1);
		}
        rotate(x);
    }
    if (goal==0) root=x;
}
inline int Kth(int k) {
    int p=root;
    while (666233) {
        pushdown(p);
        if (size[ch[p][0]]>=k) p=ch[p][0];
        else if (size[ch[p][0]]+1==k) return p;
        else k-=size[ch[p][0]]+1,p=ch[p][1];
    }
}
void build(int &p,int l,int r,int ff) {
	if (l>r) {p=0;return;}
	p=++num;
	fa[p]=ff;
	if (l==r) {
		size[p]=1;
		ch[p][0]=ch[p][1]=0;
		if (l==0 || l==n+1) mx[p]=val[p]=-1e9;
		return;
	}
	int mid=(l+r)>>1;
	if (mid==0 || mid==n+1) mx[p]=val[p]=-1e9;
	build(ch[p][0],l,mid-1,p);
	build(ch[p][1],mid+1,r,p);
	update(p);
}
int main() {
	cin >> n >> m;
	build(root,0,n+1,0);mx[0]=-1e9;
	for (int i=1;i<=m;i++) {
		int op,x,y,v=0;
		scanf("%d%d%d",&op,&x,&y);
		if (op==1) scanf("%d",&v);
		int la=Kth(x);splay(la,0);//x+1-1
		int ne=Kth(y+2);splay(ne,la);//y+1+1
		int p=ch[ne][0];
		if (op==1) tag[p]+=v,mx[p]+=v,val[p]+=v;
		else if (op==2) reversed[p]^=1;
		else printf("%d\n",mx[p]);
	}
	return 0;
}

其他操作

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
inline void ins(int c) {
    int p=root,ff=0;
    while (p && key[p]!=c) {
        ff=p;
        p=ch[p][c>key[p]];
    }
    if (p) cnt[p]++;
    else {
        p=++num;
        if (ff) ch[ff][c>key[ff]]=p;//如果父节点非0
	else root=p;
        ch[p][0]=ch[p][1]=0;
        fa[p]=ff;
        key[p]=c;
        cnt[p]=size[p]=1;
    }
    splay(p,0);
}

inline void find(int c) { //查找c的位置，并将其旋转到根节点
    int p=root;
    while (ch[p][c>key[p]] && c!=key[p]) p=ch[p][c>key[p]];
    splay(p,0);
}

inline int pre_nxt(int c,int op) { //查找c的前驱(0)或者后继(1)
    find(c);
    int p=root;
	if (key[p]!=c) { //c不存在需要特判
		if (key[p]>c && op) return p;
	    if (key[p]<c && !op) return p;
	}
    p=ch[p][op];
    while (ch[p][op^1]) p=ch[p][op^1];
    return p;
}

inline void del(int c) {
	find(c);
	if (key[root]!=c) return;
	if (cnt[root]>1) {cnt[root]--;size[root]--;return;}
	if (!ch[root][0] && !ch[root][1]) {root=0;return;}
	if (!ch[root][0]) {root=ch[root][1];fa[root]=0;return;}
	if (!ch[root][1]) {root=ch[root][0];fa[root]=0;return;}
	int p=pre_nxt(c,0),oldroot=root;
	splay(p,0);
	fa[ch[oldroot][1]]=root;
	ch[root][1]=ch[oldroot][1];
	update(root);
}

还有合并，拆分等操作未写出