先上一波题目 https://vjudge.net/contest/338760#problem/L
这道题我们维护一个双向链表 操作1 2 3 都是双向链表的基本操作 4操作考虑到手动将链表反转时间复杂度太高
我们可以不反转序列 而反转“操作” 如反转之后其实就是将操作1和2互换 对操作三没有影响 、
在求和的时候 我们可以先按正常顺序求出奇数位置的数的和
而如果数列长度为奇数 反转前后奇数位置的数的和不变
如果数列长度为偶数 反转奇数次之后 奇偶位置改变 这个时候我们只需要将总和减去偶数位置的和就是答案了
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<cmath> #define LL long long using namespace std; const int M=1e6+7; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } int n,m,flg,c; int l[M],r[M],cnt; void lnk(int x,int y){r[x]=y; l[y]=x;} int main(){ int x,y; while(scanf("%d %d",&n,&m)!=EOF){ flg=0; for(int i=1;i<=n;i++) l[i]=i-1,r[i]=i+1; r[0]=1; l[0]=-1; l[n+1]=n; r[n+1]=-1; for(int i=1;i<=m;i++){ c=read(); if(c==4){flg^=1; continue;} x=read(); y=read(); if(flg&&c<=2) c=3-c; if(c==1&&l[y]==x) continue; if(c==2&&r[y]==x) continue; int lx=l[x],rx=r[x],ly=l[y],ry=r[y]; if(c==1) lnk(lx,rx),lnk(ly,x),lnk(x,y); else if(c==2) lnk(lx,rx),lnk(y,x),lnk(x,ry); else if(c==3){ if(l[y]==x) lnk(lx,y),lnk(y,x),lnk(x,ry); else if(r[y]==x) lnk(ly,x),lnk(x,y),lnk(y,rx); else lnk(lx,y),lnk(y,rx),lnk(ly,x),lnk(x,ry); } } LL ans=0,now=0; for(int i=1;i<=n;i++){ now=r[now]; if(i&1) ans+=now; } if(flg&&n%2==0) ans=(LL)n*(n+1)/2-ans; printf("Case %d: %lld\n",++cnt,ans); } return 0; }