2016CCPC东北地区大学生程序设计竞赛 - 重现赛

#include #include #include #include #include #include #include #include #include

using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P;

#define bug printf("*********\n"); #define debug(x) cout<<"["<

const long long mod=1e9+7; const int maxn=5e5+5; const int INF=0x7fffffff; const int inf=0x3f3f3f3f; const double eps=1e-8;

int a[maxn]; int l,r; int t,cas=1; int Q; char s[100]; deque q; int main() { scanf("%d",&t); while(t--) { scanf("%d",&Q); int x; bool b=1; l=r=2e5+5; printf("Case #%d:\n",cas++); q.clear(); while(Q--) { scanf("%s",s); if(b) { if(s[0]=='P'&&s[1]=='U') { scanf("%d",&x); a[++r]=x;

if(x==0)q.push_back(r);

} else if(s[0]=='Q') { if(r==l)printf("Invalid.\n"); else if(r-l==1)printf("%d\n",a[r]); else { if(q.size()==0) { printf("%d\n",(r-l)&1); } else { int k=q.front(); if(r==k)printf("%d\n",(k-l+1)&1); else printf("%d\n",(k-l)&1); }

}

} else if(s[0]=='R') { b=0;

} else { if(a[r]==0)q.pop_back(); --r;

} } else { if(s[0]=='P'&&s[1]=='U') { scanf("%d",&x); a[l--]=x; if(x==0)q.push_front(l+1);

#include #include #include #include #include #include #include #include #include

using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P;

#define bug printf("*********\n"); #define debug(x) cout<<"["<

const long long mod=1e9+7; const int maxn=5e5+5; const int INF=0x7fffffff; const int inf=0x3f3f3f3f; const double eps=1e-8;

int g[maxn<<4],c[maxn]; int f[maxn<<4],a[maxn],aa[maxn],b[maxn],bb[maxn]; int A,B,n,m;

long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); }

void build(int l,int r,int k) { if(r-l==1) { g[k]=c[r]; } else { build(lson); build(rson); g[k]=gcd(g[chl],g[chr]); } }

int findleft(int l,int r,int k,int u,int v) { if(r<=u) { if(gcd(g[k],v)==v)return 0; if(l+1==r)return r; int x=findleft(rson,u,v); if(x)return x; else return findleft(lson,u,v); } if(u>mid) { int x=findleft(rson,u,v); if(x)return x; } return findleft(lson,u,v); }

void getleft(int x) { A=0; for(int i=c[x],j=x,k; j!=0; j=k) { k=findleft(0,n,0,j,i); a[A]=j-k; aa[A++]=i; if(k==0)return ; i=gcd(c[k],i); } return ; } int findright(int l,int r,int k,int u,int v) { //这个是用线段树往左找GCD if(l+1>=u) { if(gcd(g[k],v)==v)return n+1; if(l+1==r)return r; int x = findright(lson,u,v); if(x<=n)return x; else return findright(rson,u,v); } if(u<=mid) { int x=findright(lson,u,v); if(x<=n)return x; } return findright(rson,u,v); }

void getright(int x) { B=0; for(int i= c[x],j=x,k; j<=n; j=k) { //这个是暴力X所有左边的GCD k=findright(0,n,0,j,i); b[B]=k-j; bb[B++]=i; i=gcd(c[k],i); } return ; } void change(int l,int r,int k,int u,int v) { if (l+1==r) { g[k] = v; return; } if (u<=mid) change(lson,u,v); else change(rson,u,v); g[k]=gcd(g[chl],g[chr]); }

int main() { int t,cas=1; scanf("%d",&t); while(t--) { printf("Case #%d:\n",cas++); scanf("%d%d",&n,&m); for(int i=1; i<=n; ++i)scanf("%d",&c[i]); build(0,n,0); //初始化线段树 memset(f,0,sizeof(f)); int ans=0; for(int i=1; i<=n; i++) { getleft(i); //初始化只要找所有i左边的GCD或者右边也可以，但是只能找一边不然会重复。

#include #include #include #include #include #include #include #include #include

using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair P;

#define bug printf("*********\n"); #define debug(x) cout<<"["<