來自FallDream的博客，未經允許，請勿轉載，謝謝。

---------------------------------------------------

ditoly這次打好了虐爆我們的主意，掏出三道喪題，囊括三種賽制，第一道喪病oi題，第二道sb交互題，第三道奇怪提答............

第二道交互題沒人做，也挺奇怪的，不講了；

第三道是找規律，也就50個數列把，我拿出我最強的找規律水平，用上插值啊快速冪啊矩陣乘法啊肉眼觀察法啊亂差分啊等等辦法，騙到了48分，貌似全場最高了..得分靠隨緣，也不講了。

講講第一題，給定一個數列，需要支持100種操作。??? $n,m\leqslant 100000$

1:查詢一段區間，你每次可以任選其中一段區間+1或者-1，求把它變成全是0的最小次數。

10:區間加一個值。? 11:區間翻轉?? 100：回到k次操作之前的狀態。??

看到這題，很明顯可以可持久化平衡樹，但我姿勢不夠，不會，而且喪病出題人卡空間。還好腦補了一種亂建邊的方法，從一個狀態向它能轉移到的狀態連邊，然后dfs，離開時撤銷，類似線段樹分治。

然后維護一棵平衡樹，修改操作容易維護，查詢操作的答案是這個區間差分的絕對值之和加上左右端點的絕對值之和除以2.? 我把查詢做成了只能-1，爆0了qaq

#include<iostream> #include<cstdio> #define MN 100000 #define ll long long using namespace std; inline int read() {int x = 0 , f = 1; char ch = getchar();while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f; }int s[MN+5],n,m,cnt=0; struct ques{int kind,l,r,x;ll ans;}q[MN+5]; struct edge{int to,next;}e[MN+5]; int fa[MN+5],c[MN+5][2],rt,head[MN+5],size[MN+5]; ll num[MN+5],ad[MN+5],nl[MN+5],nr[MN+5],sum[MN+5]; bool rev[MN+5];template<typename t> t abs(t x){return x<0?-x:x;} inline void ins(int f,int t){e[++cnt]=(edge){t,head[f]};head[f]=cnt;}void update(int x) {int l=c[x][0],r=c[x][1];nl[x]=(l?nl[l]:num[x]);nr[x]=(r?nr[r]:num[x]);size[x]=size[l]+size[r]+1;sum[x]=0;if(l) sum[x]+=sum[l]+abs(num[x]-nr[l]);if(r) sum[x]+=sum[r]+abs(num[x]-nl[r]); }inline void mark(int x,int z) {nl[x]+=z;nr[x]+=z;num[x]+=z;ad[x]+=z; }void pushdown(int x) {int l=c[x][0],r=c[x][1];if(rev[x]) {rev[l]^=1;rev[r]^=1;rev[x]^=1;swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);swap(nl[l],nr[l]);swap(nl[r],nr[r]);}if(ad[x]){mark(l,ad[x]);mark(r,ad[x]);ad[x]=0;} }void build(int&x,int l,int r,int last) {if(l>r) return;x=l+r>>1;fa[x]=last;num[x]=s[x];if(l==r) {size[x]=1;nl[x]=nr[x]=s[x];sum[x]=0;return;}build(c[x][0],l,x-1,x);build(c[x][1],x+1,r,x);update(x); }void rotate(int x,int&k) {int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;if(y==k) k=x; else c[z][c[z][1]==y]=x;fa[x]=z;fa[y]=x;fa[c[x][r]]=y;c[y][l]=c[x][r];c[x][r]=y;update(y);update(x); }void splay(int x,int&k) {while(x!=k){int y=fa[x],z=fa[y];if(y!=k){if(c[z][1]==y^c[y][1]==x) rotate(x,k);else rotate(y,k); } rotate(x,k);} }int find(int x,int rk) {pushdown(x);int sz=size[c[x][0]]+1;if(sz==rk) return x;else if(sz<rk) return find(c[x][1],rk-sz);else return find(c[x][0],rk); }int split(int l,int r) {splay(find(rt,l),rt);splay(find(rt,r),c[rt][1]);return c[c[rt][1]][0]; }void solve(int x) {if(q[x].kind==1) {ll y=sum[split(q[x].l,q[x].r+2)];q[x].ans=(1LL*abs(num[find(rt,q[x].l+1)])+abs(num[find(rt,q[x].r+1)])+y)/2;}if(q[x].kind==10){int y=split(q[x].l,q[x].r+2);mark(y,q[x].x); update(c[rt][1]);update(rt);}if(q[x].kind==11) {int y=split(q[x].l,q[x].r+2);rev[y]^=1;swap(c[y][0],c[y][1]);swap(nl[y],nr[y]);update(c[rt][1]);update(rt);}for(int i=head[x];i;i=e[i].next)solve(e[i].to);if(q[x].kind==10){int y=split(q[x].l,q[x].r+2);mark(y,-q[x].x); update(c[rt][1]);update(rt);}if(q[x].kind==11){int y=split(q[x].l,q[x].r+2);rev[y]^=1;swap(c[y][0],c[y][1]);swap(nl[y],nr[y]);update(c[rt][1]);update(rt);} }int main() {n=read();m=read();for(int i=1;i<=n;i++)s[i+1]=read();for(int i=1;i<=m;i++){q[i].kind=read();if(q[i].kind==1) q[i].l=read(),q[i].r=read();if(q[i].kind==10) q[i].l=read(),q[i].r=read(),q[i].x=read();if(q[i].kind==11) q[i].l=read(),q[i].r=read();if(q[i].kind==100) q[i].x=read(),ins(i-q[i].x-1,i);else ins(i-1,i);}cnt=0;build(rt,1,n+2,0);solve(0);for(int i=1;i<=m;i++)if(q[i].kind==1)printf("%lld\n",q[i].ans);return 0; }

?

轉載于:https://www.cnblogs.com/FallDream/p/xunlian330.html

總結

以上是生活随笔為你收集整理的[3.30校内训练赛]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。