usaco 2008 月賽 lites 開關燈 題解

  題目：     Farmer John嘗試通過和奶牛們玩益智玩具來保持他的奶牛們思維靈活. 其中一個大型玩具是 牛欄中的燈. 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之間的燈有多少是亮着的. 幫助FJ確定他的奶牛們可以得到正确的答案. 

這是我做的第一道線段樹的題目，以前隻了解過模闆——下面我就來介紹一下。

-------------------------------------------線段樹的介紹-------------------------------------------------------

線段樹是什麼？就是一種二叉樹結構，而且它的每一個結點代表一條線段的和。

以下是百度百科的詳細解釋：

線段樹是一種 二叉搜尋樹，與 區間樹相似，它将一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。 對于線段樹中的每一個非 葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。是以線段樹是 平衡二叉樹，最後的子節點數目為N，即整個線段區間的長度。 使用線段樹可以快速的查找某一個節點在若幹條線段中出現的次數，時間複雜度為O(logN）。而未優化的 空間複雜度為2N，是以有時需要離散化讓空間壓縮。 線段樹至少支援下列操作： Insert(t,x）：将包含在區間 int 的元素 x 插入到樹t中； Delete(t,x）：從線段樹 t 中删除元素 x； Search(t,x）：傳回一個指向樹 t 中元素 x 的指針。

一般線段樹我都是用堆來儲存的，即a[i]的左兒子是a[i*2]，右兒子是a[i*2+1]。

線段樹快在哪裡呢？他對于每個結點的修改和通路都是log(n)的效率。

相信到這裡都很好了解，下面介紹一種更加強大的思想：lazy思想。

如果我要将a--b的區間的每一個值都加上p，那麼效率就是(b-a+1)log(n)。有沒有更快的方法呢？

通過研究，我們發現：如果它隻修改而并不通路，我們豈不是不用更新了！

于是我們可以再開一個域cnt，表示目前有多少次累加被積壓着。每次處理到k結點時（注意，這個處理包括通路和修改等），我們都把它積壓的值給加上，然後傳給它的兒子。此時它的兒子不必處理，直到要處理到它的兒子為止。

下面是這強大的update代碼：

void update(long k)
{
  if (a[k].cnt==0) return;
  a[k].sum+=(a[k].r-a[k].l+1)*a[k].cnt;
  a[k*2].cnt+=a[k].cnt;a[k*2+1].cnt+=a[k].cnt;
  a[k].cnt=0;
}
           

每次處理到k時，先做一遍update(k)再進行操作即可。

------------------------------------------------回到原題-------------------------------------------------------

這裡可能相對簡單一些，下面說一些與模闆不太相同的細節。

（1）初始建樹時，每個值都是0.

（2）在插入時，每次cnt累加1即可，這個1當然不是加上1，而是執行操作數。

（3）在update中，如果cnt是偶數，就可以直接清零（因為偶數次不是抵消了嘛！）；如果是奇數，我們把它相反一下，并向下傳1。

代碼：

#include<stdio.h>
using namespace std;
const long maxn=100001;
struct tree
{
  long l,r;                       //l和r就是a[i]所表示的左右區間範圍。
  long cnt,sum;                   //cnt是累加的操作次數，sum是a[i]表示的線段中開着的燈的數量。
}a[4*maxn];
long n,m,i,x,y,ok;
void build(long k,long l,long r)   //基礎建樹
{
  a[k].cnt=0;a[k].l=l;a[k].r=r;
  if (l==r) return;
  long mid=(l+r)/2;
  build(k*2,l,mid);build(k*2+1,mid+1,r);
}
void update(long k)       //update操作。
{
  if (a[k].cnt==0) return;
  if (a[k].cnt%2==1) 
  {
    a[k].sum=a[k].r-a[k].l+1-a[k].sum;       //a[k]的區間是a[k].l到a[k].r，那麼共有a[k].r-a[k].l+1個，這裡取反。
    a[k*2].cnt+=1;a[k*2+1].cnt+=1;
    a[k].cnt=0;
  }
  else a[k].cnt=0;
}
void ins(long k,long l,long r)
{
  update(k);
  if (a[k].l>=l&&a[k].r<=r) {a[k].cnt+=1;return;}   //目前區域被覆寫
  long mid=(a[k].l+a[k].r)/2;                      //二分找被覆寫的區域。
  if (l<=mid) ins(k*2,l,r);
  if (r>mid) ins(k*2+1,l,r);
  update(k*2);update(k*2+1);        //對兒子的更新操作（很重要），因為下面一步要重新更新目前的值。
  a[k].sum=a[k*2].sum+a[k*2+1].sum;
}
long find(long k,long l,long r)             //這與ins大同小異。
{
  update(k);                    
  if (a[k].l>=l&&a[k].r<=r) return a[k].sum;
  long mid=(a[k].l+a[k].r)/2,o=0;
  if (l<=mid) o+=find(k*2,l,r);
  if (r>mid) o+=find(k*2+1,l,r);
  update(k*2);update(k*2+1);
  a[k].sum=a[k*2].sum+a[k*2+1].sum;
  return o;
}
int main()
{
    //freopen("lites.in","r",stdin);
    //freopen("lites.out","w",stdout);
    scanf("%ld%ld",&n,&m);
    build(1,1,n);
    for (i=1;i<=m;i++)
    {
      scanf("%ld%ld%ld",&ok,&x,&y);
      if (ok==0) ins(1,x,y);
      else {long ans=find(1,x,y);printf("%ld\n",ans);}
    }
    //scanf("%ld",&n,&m);
    return 0;
}