CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_654_div._2 [2020/07/02 11:13]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_654_div._2 [2020/08/01 10:15] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:cf_654_div._2被移动至2020-2021:teams:legal_string:jxm2001:contest:cf_654_div._2
@@ 行 33: / 行 33: @@
 <hidden 查看代码>
 <code cpp>
-#include <cstdio>
-#include <iostream>
-#include <vector>
-#include <algorithm>
-#include <cstring>
-#include <cctype>
-#include <queue>
-#include <cmath>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset((a),(b),sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5;
 int a[MAXN],b[MAXN<<1];
@@ 行 100: / 行 66: @@
 	else
 	enter(0);
+	return 0;
+}
+</code>
+</hidden>
+==== 题解 $2$ ====
+$f(x)=\prod_{i=0}^{n-1} C_i(x)=\prod_{i=0}^{n-1} b_{x+i}-i=\prod_{i=x}^{x+n-1} b_{i}-i+x$。
+所以 $p\nmid f(x)\iff$ 对所有 $x\le i\lt x+n$，有 $x$ 与 $i-b_{i}$ 不同余 $\iff$ $x-(A-n)$ 与 $i-(A-n)-b_{i}$ 不同余。
+暴力枚举 $A-n\lt x\lt A$，考虑 $i-b_{i}$ 对于 $x$ 与 $x-1$ 的约束只用一项不同，所以可以用滑动窗口维护。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5;
+int a[MAXN],b[MAXN<<1],c[MAXN],ans[MAXN],cnt;
+int mod(int a,int p){return (a%p+p)%p;}
+int main()
+{
+	int n=read_int(),p=read_int(),A=0;
+	_for(i,0,n){
+		a[i]=read_int();
+		A=max(A,a[i]);
+	}
+	_for(i,0,n)
+	b[max(0,a[i]-(A-n))]++;
+	_for(i,1,n<<1)
+	b[i]+=b[i-1];
+	_for(i,0,n)
+	c[mod(i-b[i],p)]++;
+	_for(i,1,n){
+		c[mod(i-1-b[i-1],p)]--;
+		c[mod(i+n-1-b[i+n-1],p)]++;
+		if(!c[i%p])
+		ans[cnt++]=i+A-n;
+	}
+	enter(cnt);
+	_for(i,0,cnt){
+		if(i)
+		putchar(' ');
+		write(ans[i]);
+	}
 	return 0;
 }
@@ 行 109: / 行 118: @@
 ==== 题意 ====
+<del>题目太长了，所以省略了</del>
 ==== 题解 ====
+序列操作，很明显用线段树维护。
+每个区间考虑维护该区间的前缀和后缀以及非前后缀的最大答案。
+同时每个区间还需要维护一个 $\text{type}$ 参数来区间是有前后缀的区间还是不分前后缀的区间。
+关于区间合并，考虑将 '< >' 可作为串的划分标志，'<' 左边的串和 '>' 右边的串互不关联。
+另外每个线段树结点需要同时维护两个区间，一个为正常区间，一个为 '<' 和 '>' 互换的区间，便于修改和查询操作。
+还有关于 $\text{push_up}$ 操作要注意提前下放子节点的懒标记，否则会出错。
+时间复杂度 $O(n+q\log n)$，细节见代码。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=5e5+5;
+struct Node{
+	int str[2][2],ans;
+	bool type;
+}node[MAXN<<2][2];
+int lef[MAXN<<2],rig[MAXN<<2];
+bool isleaf[MAXN<<2],lazy[MAXN<<2];
+char buf[MAXN];
+Node merge(const Node &lef,const Node &rig){
+	Node temp;
+	temp.ans=max(lef.ans,rig.ans);
+	if(lef.type&&rig.type){
+		temp.type=true;
+		temp.str[0][0]=lef.str[0][0];
+		temp.str[0][1]=lef.str[0][1];
+		temp.str[1][0]=rig.str[1][0];
+		temp.str[1][1]=rig.str[1][1];
+		if(lef.str[1][1]&&rig.str[0][0])
+		temp.ans=max(max(lef.str[1][0]+lef.str[1][1],rig.str[0][0]+rig.str[0][1]),temp.ans);
+		else
+		temp.ans=max(lef.str[1][0]+lef.str[1][1]+rig.str[0][0]+rig.str[0][1],temp.ans);
+	}
+	else if(lef.type){
+		temp.type=true;
+		temp.str[0][0]=lef.str[0][0];
+		temp.str[0][1]=lef.str[0][1];
+		if(lef.str[1][1]&&rig.str[0][0]){
+			temp.ans=max(lef.str[1][0]+lef.str[1][1],temp.ans);
+			temp.str[1][0]=rig.str[0][0];
+			temp.str[1][1]=rig.str[0][1];
+		}
+		else{
+			temp.str[1][0]=lef.str[1][0]+rig.str[0][0];
+			temp.str[1][1]=lef.str[1][1]+rig.str[0][1];
+		}
+	}
+	else if(rig.type){
+		temp.type=true;
+		temp.str[1][0]=rig.str[1][0];
+		temp.str[1][1]=rig.str[1][1];
+		if(lef.str[0][1]&&rig.str[0][0]){
+			temp.ans=max(rig.str[0][0]+rig.str[0][1],temp.ans);
+			temp.str[0][0]=lef.str[0][0];
+			temp.str[0][1]=lef.str[0][1];
+		}
+		else{
+			temp.str[0][0]=lef.str[0][0]+rig.str[0][0];
+			temp.str[0][1]=lef.str[0][1]+rig.str[0][1];
+		}
+	}
+	else{
+		if(lef.str[0][1]&&rig.str[0][0]){
+			temp.type=true;
+			temp.str[0][0]=lef.str[0][0];
+			temp.str[0][1]=lef.str[0][1];
+			temp.str[1][0]=rig.str[0][0];
+			temp.str[1][1]=rig.str[0][1];
+		}
+		else{
+			temp.type=false;
+			temp.str[0][0]=lef.str[0][0]+rig.str[0][0];
+			temp.str[0][1]=lef.str[0][1]+rig.str[0][1];
+			temp.str[1][0]=temp.str[1][1]=0;
+		}
+	}
+	return temp;
+}
+void push_down(int k){
+	if(lazy[k]){
+		swap(node[k][0],node[k][1]);
+		lazy[k]=false;
+		if(!isleaf[k])
+		lazy[k<<1]^=1,lazy[k<<1|1]^=1;
+	}
+}
+void push_up(int k){
+	push_down(k<<1);push_down(k<<1|1);
+	node[k][0]=merge(node[k<<1][0],node[k<<1|1][0]);
+	node[k][1]=merge(node[k<<1][1],node[k<<1|1][1]);
+}
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	int M=L+R>>1;
+	if(L==R){
+		isleaf[k]=true;
+		if(buf[M]=='<'){
+			node[k][0].str[0][1]=1;
+			node[k][1].str[0][0]=1;
+		}
+		else{
+			node[k][0].str[0][0]=1;
+			node[k][1].str[0][1]=1;
+		}
+		return;
+	}
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+	push_up(k);
+}
+void update(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)
+	return lazy[k]^=1,void();
+	push_down(k);
+	int mid=lef[k]+rig[k]>>1;
+	if(mid<L)
+	update(k<<1|1,L,R);
+	else if(mid>=R)
+	update(k<<1,L,R);
+	else{
+		update(k<<1,L,R);
+		update(k<<1|1,L,R);
+	}
+	push_up(k);
+}
+Node query(int k,int L,int R){
+	push_down(k);
+	if(L<=lef[k]&&rig[k]<=R)
+	return node[k][0];
+	int mid=lef[k]+rig[k]>>1;
+	if(mid<L)
+	return query(k<<1|1,L,R);
+	else if(mid>=R)
+	return query(k<<1,L,R);
+	else
+	return merge(query(k<<1,L,R),query(k<<1|1,L,R));
+}
+int main()
+{
+	int n=read_int(),q=read_int(),l,r;
+	Node temp;
+	scanf("%s",buf+1);
+	build(1,1,n);
+	while(q--){
+		l=read_int(),r=read_int();
+		update(1,l,r);
+		temp=query(1,l,r);
+		enter(max(temp.ans,max(temp.str[0][0]+temp.str[0][1],temp.str[1][0]+temp.str[1][1])));
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具