codevs 1690 開關燈

USACO

?時間限制: 1 s ?空間限制: 128000 KB ?題目等級 : 鉆石 Diamond 題目描述?Description

? ? YYX家門前的街上有N(2<=N<=100000)盞路燈，在晚上六點之前，這些路燈全是關著的，六點之后，會有M(2<=m<=100000)個人陸續按下開關，這些開關可以改變從第i盞燈到第j盞燈的狀態，現在YYX想知道，從第x盞燈到第y盞燈中有多少是亮著的(1<=i,j,x,y<=N)

輸入描述?Input Description 第 1 行: 用空格隔開的兩個整數N和M 第 2..M+1 行: 每行表示一個操作, 有三個用空格分開的整數: 指令號(0代表按下開關，1代表詢問狀態), x 和 y? 輸出描述?Output Description

第 1..詢問總次數 行:對于每一次詢問，輸出詢問的結果

樣例輸入?Sample Input

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

樣例輸出?Sample Output 1
2 1 /*沒什么好說的，線段樹的區間修改加區間查詢*/ 2 #define N 100100 3 #include<iostream> 4 using namespace std; 5 #include<cstdio> 6 #include<cstring> 7 struct Tree{ 8 int sum,delta,l,r; 9 }tree[N*4]; 10 int n,m,a,x,y; 11 void update(int k) 12 { 13 int lch=k<<1,rch=(k<<1)+1; 14 tree[k].sum=tree[lch].sum+tree[rch].sum; 15 } 16 void build_tree(int k,int l,int r) 17 { 18 tree[k].l=l;tree[k].r=r; 19 if(l==r) 20 { 21 tree[k].sum=tree[k].delta=0; 22 return ; 23 } 24 int mid=(l+r)>>1,lch=k<<1,rch=(k<<1)+1; 25 build_tree(lch,l,mid); 26 build_tree(rch,mid+1,r); 27 update(k); 28 } 29 void down(int k) 30 { 31 int lch=k<<1,rch=(k<<1)+1; 32 tree[lch].delta+=tree[k].delta; 33 tree[lch].delta%=2; 34 tree[lch].sum=(tree[lch].r-tree[lch].l+1)-tree[lch].sum; 35 tree[rch].delta+=tree[k].delta; 36 tree[rch].delta%=2; 37 tree[rch].sum=(tree[rch].r-tree[rch].l+1)-tree[rch].sum; 38 tree[k].delta=0; 39 } 40 void change(int k,int l,int r,int x,int y) 41 { 42 if(x<=l&&r<=y) 43 { 44 tree[k].delta++; 45 tree[k].delta%=2; 46 tree[k].sum=(r-l+1)-tree[k].sum; 47 return; 48 } 49 if(tree[k].delta) 50 down(k); 51 int mid=(l+r)>>1,lch=k<<1,rch=(k<<1)+1; 52 if(x<=mid) 53 change(lch,l,mid,x,y); 54 if(y>mid) 55 change(rch,mid+1,r,x,y); 56 update(k); 57 } 58 int query(int k,int l,int r,int x,int y) 59 { 60 if(x<=l&&r<=y) 61 { 62 return tree[k].sum; 63 } 64 if(tree[k].delta) 65 down(k); 66 int mid=(l+r)>>1,lch=k<<1,rch=(k<<1)+1; 67 int ans=0; 68 if(x<=mid) 69 ans+=query(lch,l,mid,x,y); 70 if(y>mid) 71 ans+=query(rch,mid+1,r,x,y); 72 return ans; 73 } 74 int main() 75 { 76 scanf("%d%d",&n,&m); 77 build_tree(1,1,n); 78 for(int i=1;i<=m;++i) 79 { 80 scanf("%d%d%d",&a,&x,&y); 81 if(a==0) 82 { 83 change(1,1,n,x,y); 84 } 85 else printf("%d\n",query(1,1,n,x,y)); 86 } 87 return 0; 88 }

?

轉載于:https://www.cnblogs.com/c1299401227/p/5492875.html

總結

以上是生活随笔為你收集整理的线段树--codevs 1690 开关灯的全部內容，希望文章能夠幫你解決所遇到的問題。

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