线段树3——一些例题的题解

 

 

这篇博客主要是由一些题目的题解构成的

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——一些例题的题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。