跟昨天那個自己寫的，沒有按照模板來的一看風格就不相類似，今天模擬賽的時候就是用的我的那個自己YY的代碼，才拿了10分。個人認為關鍵的問題應該在於對於數據的處理太過繁瑣了，所以回來之後，就拿了大佬的程式對照著改。在這裡不得不吐槽一下c++的讀入，cin40分，scanf滿分。還是模板的線段樹比較清晰， ...
跟昨天那個自己寫的，沒有按照模板來的一看風格就不相類似，今天模擬賽的時候就是用的我的那個自己YY的代碼，才拿了10分。個人認為關鍵的問題應該在於對於數據的處理太過繁瑣了，所以回來之後，就拿了大佬的程式對照著改。在這裡不得不吐槽一下c++的讀入，cin40分，scanf滿分。還是模板的線段樹比較清晰，決定以後就用這種了。
開關燈 源文件： lites.cpp/.c/.pas 輸入文件： lites.in 輸出文件： lites.out 時限： 1s 空間： 256M 【題目描述】 小Y嘗試通過和奶牛們玩益智玩具來保持他的奶牛們思維敏捷，其中一個大型玩具是牛欄中的燈。 N (2<= N <= 100,000) 頭奶牛中的每一頭被連續的編號為1..N, 站在一個彩色的燈下麵。剛到傍晚的時候, 所有的燈都是關閉的。奶牛們通過N個按鈕來控制燈的開關，按第i個按鈕可以改變第i個燈的狀態。 奶牛們執行M (1<= M <= 100,000)條指令, 每個指令都是兩個整數中的一個(0<= 指令號<= 1)。 第1種指令(用0表示)包含兩個數字S_i和E_i (1<= S_i<= E_i<= N), 它們表示起始開關和終止開關。奶牛們只需要把從S_i到E_i之間的按鈕都按一次, 就可以完成這個指令。 第2種指令(用1表示)同樣包含兩個數字S_i和E_i (1<= S_i<= E_i<= N), 不過這種指令是詢問從S_i到E_i之間的燈有多少是亮著的。 請你幫助小Y確保他的奶牛們可以得到正確的答案。 【輸入格式】 第 1 行: 用空格隔開的兩個整數N和M。 第 2..M+1 行: 每行表示一個操作, 有三個用空格分開的整數: 指令號, S_i 和 E_i。 【輸出格式】 對於每一次詢問, 輸出一行表示詢問的結果。 【輸入樣例】 4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4 【輸出樣例】 1 2 【樣例解釋】 一共有4盞燈，5個指令。下麵是執行的情況: 燈 1 2 3 4 Init: O OOOO = 關* = 開 0 1 2 -> * * O O改變燈 1 和 2 的狀態 0 2 4 -> * O * * 1 2 3 -> 1 輸出在2..3的範圍內有多少燈是亮的 0 2 4 -> * * O O改變燈 2 ,3 和 4 的狀態 1 1 4 -> 2 輸出在1..4的範圍內有多少燈是亮的 【數據規模】 對於40%的數據滿足：1<=N,M<=10000； 對於100%的數據滿足： 1<=N,M<=100000。
（很明顯的線段樹，開始我還很開心，因為昨天剛調出來，以為要AC了）。
下麵是自己改的代碼。
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node{ 4 int l,r,dat,lazy; 5 }shu[400010];//結構體，中間的任何一個單獨成為一個數組都是可以的，其實沒有什麼高大上的，只是看起來比較高逼格而已。 6 int n,m,a,b,c,ans;//個人建議多設全局變數，Pascal的優良傳統，比較方便，不容易錯。 7 void build_tree(int x,int y,int z){//建樹，和昨天我的代碼是一樣的（不對，是今天）。 8 shu[x].l=y; 9 shu[x].r=z; 10 if (y==z) return; 11 int o=(y+z)/2; 12 build_tree(x*2,y,o); 13 build_tree(x*2+1,o+1,z); 14 } 15 void caozuo(int x){//操作，為什麼要單獨在一個過程中呢？因為下麵兩段都要用到，更方便編程思路更清晰。 16 if (shu[x].lazy){//開燈的時候改變。也可以用bool數組。 17 shu[x*2].dat=(shu[x*2].r-shu[x*2].l+1)-shu[x*2].dat;//這是因為一部分是開的，那麼改變了之後，另一部分就是開的，這一部分是關的。 18 shu[x*2+1].dat=(shu[x*2+1].r-shu[x*2+1].l+1)-shu[x*2+1].dat; 19 if (shu[x*2].lazy) shu[x*2].lazy=0; 20 else shu[x*2].lazy=1; 21 if (shu[x*2+1].lazy) shu[x*2+1].lazy=0; 22 else shu[x*2+1].lazy=1; 23 shu[x].lazy=0;//處理完了，lazy標記還原。 24 } 25 } 26 void add_tree(int x){ 27 if (shu[x].l>=b&&shu[x].r<=c){ 28 shu[x].dat=(shu[x].r-shu[x].l+1)-shu[x].dat;//兩遍開就是關 29 if (shu[x].lazy) shu[x].lazy=0; 30 else shu[x].lazy=1; 31 return; 32 } 33 caozuo(x); 34 int o=(shu[x].l+shu[x].r)/2; 35 if(b<=o) add_tree(x*2);//如果中間數比要改變區間最左邊大或相等，查找左子樹。 36 if(c>o) add_tree(x*2+1);//如果中間數比要改變區間最右邊小，查找右子樹。 37 shu[x].dat=shu[x*2].dat+shu[x*2+1].dat;//更新父節點 38 } 39 void find_tree(int x){//查找區間和。 40 if (shu[x].l>=b&&shu[x].r<=c){//在要查區間內就加上對應區間和，不用往下找，因為子結點的區間在父節點的區間之內，不應該重覆。 41 ans=ans+shu[x].dat; 42 return; 43 } 44 caozuo(x); 45 int o=(shu[x].l+shu[x].r)/2; 46 if(b<=o) find_tree(x*2); 47 if(c>o) find_tree(x*2+1); 48 return; 49 } 50 int main(){ 51 scanf("%d%d",&n,&m); 52 build_tree(1,1,n); 53 for (int i=1;i<=m;i++){ 54 scanf("%d%d%d",&a,&b,&c); 55 if (a==0){ 56 add_tree(1); 57 } 58 else { 59 ans=0; 60 find_tree(1); 61 printf("%d\n",ans); 62 } 63 } 64 return 0; 65 }
難點是如何處理開著燈的數量，這就要求我們在更新的過程中，對lazy進行處理。
