?

?

這篇博客主要是由一些題目的題解構成的

1.XOR的藝術

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

本題就是一個線段樹的簡單變形，把懶標記改成異或值就行了。

注意點：1.在下傳標記的時候，區間值修改為區間總值減去原先值（t[rt].v=r-l+1-t[rt].v）

2.讀入時用scanf("%1d"&t[rt].v);就行了

代碼：

1 #include<bits/stdc++.h> 2 3 #define rd(x) x=read() 4 #define N 200005 5 6 using namespace std; 7 8 int n,m; 9 struct T{ 10 int l,r,mid,v,tag; 11 }t[N<<2]; 12 13 inline int read() 14 { 15 int f=1,x=0;char s=getchar(); 16 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 17 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 18 return x*f; 19 } 20 21 void pushdown(int rt,int len) 22 { 23 if(t[rt].tag) 24 { 25 t[rt<<1].tag^=1; 26 t[rt<<1|1].tag^=1;//異或 27 t[rt<<1].v=(len-(len>>1))-t[rt<<1].v; 28 t[rt<<1|1].v=(len>>1)-t[rt<<1|1].v;//t[rt].v=r-l+1-t[rt].v的變形 29 t[rt].tag=0; 30 } 31 } 32 33 void build(int rt,int l,int r) 34 { 35 int mid=(l+r)>>1; 36 t[rt].l=l,t[rt].r=r,t[rt].mid=mid,t[rt].tag=0; 37 if(l==r) 38 { 39 scanf("%1d",&t[rt].v); 40 return; 41 } 42 build(rt<<1,l,mid); 43 build(rt<<1|1,mid+1,r); 44 t[rt].v=t[rt<<1].v+t[rt<<1|1].v; 45 }//建樹 46 47 void update(int rt,int l,int r) 48 { 49 if(l<=t[rt].l&&t[rt].r<=r) 50 { 51 t[rt].tag^=1; 52 t[rt].v=t[rt].r-t[rt].l+1-t[rt].v; 53 return; 54 } 55 pushdown(rt,t[rt].r-t[rt].l+1); 56 if(l<=t[rt].mid)update(rt<<1,l,r); 57 if(t[rt].mid<r)update(rt<<1|1,l,r); 58 t[rt].v=t[rt<<1].v+t[rt<<1|1].v; 59 }//更新 60 int query(int rt,int l,int r) 61 { 62 if(l<=t[rt].l&&t[rt].r<=r)return t[rt].v; 63 pushdown(rt,t[rt].r-t[rt].l+1); 64 int sum=0; 65 if(l<=t[rt].mid)sum+=query(rt<<1,l,r); 66 if(t[rt].mid<r)sum+=query(rt<<1|1,l,r); 67 return sum; 68 }//查詢 69 70 int main() 71 { 72 rd(n),rd(m); 73 build(1,1,n); 74 while(m--) 75 { 76 int opt,l,r; 77 rd(opt),rd(l),rd(r); 78 if(opt)printf("%d\n",query(1,l,r)); 79 else update(1,l,r); 80 } 81 82 return 0; 83 }

?

溫馨提醒：本題有多倍經驗，在LGOJ上有另外三題

?

2.P1198 JSOI2008 最大數

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

?

本題就是板子題目，只是稍微有一點思維性。

查詢時，就是查詢cnt-n+1——cnt的區間和（其中cnt代表當前的數列個數）

修改時，就是一個普通的單點修改（注意取模）

代碼：

#include<bits/stdc++.h>#define rd(x) x=read() #define ll long longusing namespace std;ll m,d; ll ans; ll cnt;ll t[800005];inline ll read() {ll f=1,x=0;char s=getchar();while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}return x*f; }void add(int rt,int l,int r,int x,int k) {if(l==r){t[rt]=k;return;}int mid=(l+r)>>1;if(x<=mid)add(rt<<1,l,mid,x,k);else add(rt<<1|1,mid+1,r,x,k);t[rt]=max(t[rt<<1],t[rt<<1|1])%d; }//類似建樹的插入 int query(int rt,int l,int r,int x,int y) {int mid=(l+r)/2;if(x==l&&y==r)return t[rt];if(y<=mid)return query(rt<<1,l,mid,x,y);else if(x>mid)return query(rt<<1|1,mid+1,r,x,y);else return max(query(rt<<1,l,mid,x,mid),query(rt<<1|1,mid+1,r,mid+1,y)); }//查詢 int main() {rd(m),rd(d);char opt[5];ll n;for(int i=1;i<=m;i++){scanf("%s",opt);//神奇讀入方法，在這提一下，如果不想用getchar或scanf("%c ")可以用這種方法 rd(n);if(opt[0]=='A')add(1,1,m,++cnt,(n+ans)%d);//修改 else {if(n==0)ans=0;else ans=query(1,1,m,cnt-n+1,cnt)%d;//查詢 cout<<ans<<endl;}}return 0; }

?

轉載于:https://www.cnblogs.com/Robin20050901/p/10040699.html

總結

以上是生活随笔為你收集整理的线段树3——一些例题的题解的全部內容，希望文章能夠幫你解決所遇到的問題。

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