SPOJ MULTQ3 7299 Multiples of 3 （区间更新）

 题目连接：http://www.spoj.com/problems/MULTQ3/

#include <iostream>
#include <stdio.h>
#include <string.h>
#define lson rt<<1,L,mid
#define rson rt<<1|1,mid+1,R
/*
题意：给出n个数，初试为0，给出两个操作；
    0 A B ：将[A,B]区间中的每个数+1
    1 A B ：询问[A,B]区间中有多少个能被3整除的数。
思路：每个节点存储三个值：num0：整除3的个数，num1：除以3余1的个数，num2：除以3余2的个数
      更新的时候，只要将这三个值互换即可
*/
using namespace std;
const int maxn=100005;
int n,m;

struct Node{
    //num0：整除3的个数，num1：除以3余1的个数，num2：除以3余2的个数
    int num0,num1,num2;
    int lazy;  //标记该区间+1的次数，如果三次+1相当于不变
}tree[maxn<<2];

void build(int rt,int L,int R){
    tree[rt].num0=(R-L+1);
    tree[rt].num1=tree[rt].num2=0;
    tree[rt].lazy=0;
    if(L==R)
        return;
    int mid=(R+L)>>1;
    build(lson);
    build(rson);
}
void pushUp(int rt){
    tree[rt].num0=tree[rt<<1].num0+tree[rt<<1|1].num0;
    tree[rt].num1=tree[rt<<1].num1+tree[rt<<1|1].num1;
    tree[rt].num2=tree[rt<<1].num2+tree[rt<<1|1].num2;
}
void pushDown(Node &rt,Node &ls,Node &rs){
    if(rt.lazy==1){
        /*
        +1一次：
        num0->num1
        num1->num2
        num2->num0
        */
        int tmp;
        tmp=ls.num0;
        ls.num0=ls.num2;
        ls.num2=ls.num1;
        ls.num1=tmp;
        ls.lazy=(ls.lazy+rt.lazy)%3;

        tmp=rs.num0;
        rs.num0=rs.num2;
        rs.num2=rs.num1;
        rs.num1=tmp;
        rs.lazy=(rs.lazy+rt.lazy)%3;

        rt.lazy=0;
    }
    else if(rt.lazy==2){
        /*
        +1二次：
        num0->num2
        num2->num1
        num1->num0
        */
        int tmp;
        tmp=ls.num0;
        ls.num0=ls.num1;
        ls.num1=ls.num2;
        ls.num2=tmp;
        ls.lazy=(ls.lazy+rt.lazy)%3;

        tmp=rs.num0;
        rs.num0=rs.num1;
        rs.num1=rs.num2;
        rs.num2=tmp;
        rs.lazy=(rs.lazy+rt.lazy)%3;
        rt.lazy=0;
    }
}
void update(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r){
        int tmp;
        tmp=tree[rt].num0;
        tree[rt].num0=tree[rt].num2;
        tree[rt].num2=tree[rt].num1;
        tree[rt].num1=tmp;
        tree[rt].lazy=(tree[rt].lazy+1)%3;
        return;
    }
    pushDown(tree[rt],tree[rt<<1],tree[rt<<1|1]);
    int mid=(L+R)>>1;
    if(l<=mid)
        update(lson,l,r);
    if(r>mid)
        update(rson,l,r);
    pushUp(rt);
}
int query(int rt,int L,int R,int l,int r){
    if(l<=L&&R<=r){
        return tree[rt].num0;
    }
    pushDown(tree[rt],tree[rt<<1],tree[rt<<1|1]);
    int ret=0;
    int mid=(L+R)>>1;
    if(l<=mid)
        ret+=query(lson,l,r);
    if(r>mid)
        ret+=query(rson,l,r);
    return ret;
}
int main()
{
    int t,a,b;
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&t,&a,&b);
        a++;b++;
        if(t==0){
            update(1,1,n,a,b);
        }
        else{
            int ans=query(1,1,n,a,b);
            printf("%d
",ans);
        }
    }
    return 0;
}