FZU 1968 Twinkling lights III

Twinkling lights III

Time Limit: 8000ms

Memory Limit: 131072KB

This problem will be judged on FZU. Original ID: 1968
64-bit integer IO format: %I64d Java class name: Main

Twinkling lights一直以来都很好玩的游戏。或许你还记得FZU1069 Twinkling lights 和FZU1420 Twinkling lights II。现在，Bluewind改变了一下游戏规则，游戏将变得更好玩。

N盏灯排成一行，编号1..N，起初的时候，所有的灯是开着的。Bluewind将执行M个操作，操作分成五种：

C x y，把编号从x到y的灯都关掉，原来关着的灯保持不变。

S x y，把编号从x到y的灯都开起来，原来开着的灯依旧开着。

A x y，让编号从x到y的灯都改变状态，即把原来开的灯关了，原来关了的灯开起来。

Q x y，查询编号从x到y中开着的灯的个数。

L x y，查询编号从x到y中最长连续开着的灯的个数。

Input

第一行两个整数N，M（1<=N，M<=500,000）表示有N盏灯，M个操作。

接下来M行，每行按指定格式给出一个操作，其中(1<=x<=y<=N)。

Output

对于每条Q查询操作和L查询操作，输出相应的结果。

Sample Input

Sample Output

4

3

Source

Contest for 2010 lecture II

解题：线段树。。。那题HDU 3397 Sequence operation很像嘛

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int maxn = ;

 struct node {

     int lt,rt,cover;

 } tree[maxn<<];

 int ret;

 void build(int L,int R,int v) {

     tree[v].lt = L;

     tree[v].rt = R;

     tree[v].cover = ;

     if(L == R) return;

     int mid = (L + R)>>;

     build(L,mid,v<<);

     build(mid+,R,v<<|);

 }

 inline void pushup(int v) {

     if(tree[v<<].cover == tree[v<<|].cover)

         tree[v].cover = tree[v<<].cover;

     else tree[v].cover = -;

 }

 inline void pushdown(int v) {

     if(tree[v].cover >= ) {

         tree[v<<].cover = tree[v<<|].cover = tree[v].cover;

         tree[v].cover = -;

     }

 }

 void update(int lt,int rt,int val,bool sel,int v) {

     if(sel && tree[v].cover == val) return;

     if(lt <= tree[v].lt && rt >= tree[v].rt && (sel || !sel && tree[v].cover >= )) {

         if(sel) tree[v].cover = val;

         else tree[v].cover ^= ;

         return;

     }

     pushdown(v);

     if(lt <= tree[v<<].rt) update(lt,rt,val,sel,v<<);

     if(rt >= tree[v<<|].lt) update(lt,rt,val,sel,v<<|);

     pushup(v);

 }

 void query(int lt,int rt,int &ans,int &r,bool sel,int v) {

     if(!tree[v].cover) return;

     if(lt <= tree[v].lt && rt >= tree[v].rt && tree[v].cover > ) {

         if(sel) ans += tree[v].rt - tree[v].lt + ;

         else {

             if(r +  == tree[v].lt) ans += tree[v].rt - tree[v].lt + ;

             else ans = tree[v].rt - tree[v].lt + ;

         }

         r = tree[v].rt;

         ret = max(ans,ret);

         return;

     }

     pushdown(v);

     if(lt <= tree[v<<].rt) query(lt,rt,ans,r,sel,v<<);

     if(rt >= tree[v<<|].lt) query(lt,rt,ans,r,sel,v<<|);

     pushup(v);

 }

 int main() {

     int n,m,x,y,ans,r;

     char op[];

     while(~scanf("%d %d",&n,&m)) {

         build(,n,);

         while(m--) {

             scanf("%s%d%d",op,&x,&y);

             switch(op[]) {

             case 'C':

                 update(x,y,,true,);

                 break;

             case 'S':

                 update(x,y,,true,);

                 break;

             case 'A':

                 update(x,y,,false,);

                 break;

             case 'Q':

                 ret = ans = r = ;

                 query(x,y,ans,r,true,);

                 printf("%d\n",ret);

                 break;

             case 'L':

                 ret = ans = r = ;

                 query(x,y,ans,r,false,);

                 printf("%d\n",ret);

                 break;

             }

         }

     }

     return ;

 }

巴特西