hdu 4578:Transformation

題目連結如下：

Problem - 4578

目錄

方法一

方法二

方法一

參考HDU4578 線段樹多種操作的實作_4578.se_tzteyang的部落格-CSDN部落格

很自然的想法就是對加，乘，求幂的和，以及設定值分别維護懶标記，但是這樣的缺點在于，每次push_down的時候需要更新很多東西，也導緻了逾時。

方法二

參考HDU4578-Transformation （線段樹多種區間操作）_小冬囍的部落格-CSDN部落格

這裡的做法是隻維護一個區間内一樣值的節點，那麼加，乘，設定值都隻需要統一操作即可。在求幂的和的時候也隻需要區間統一求取。

代碼如下所示：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cmath>
#include<climits>

using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef long long ll;
const int MAXN=1e5+10;
const int MOD=10007;
bool flag[MAXN<<2];
ll x[MAXN<<2];

void push_up(int rt){
    if (!flag[rt<<1]||!flag[rt<<1|1]) {
        flag[rt]=false;
    } else if (x[rt<<1]!=x[rt<<1|1]){
        flag[rt]=false;
    } else {
        flag[rt]=true;
        x[rt]=x[rt<<1];
    }
}

void push_down(int rt){
    if (flag[rt]){
        flag[rt<<1]=flag[rt<<1|1]=true;
        x[rt<<1]=x[rt<<1|1]=x[rt];
        flag[rt]=false;
    }
}

void update(int ul,int ur,int op,int c,int l,int r,int rt){
//    cout<<"["<<l<<","<<r<<"]"<<endl;
    if (ul<=l && r<=ur && flag[rt]){
        if (op==1){
            x[rt]=(x[rt]+c)%MOD;
        } else if (op==2){
            x[rt]=x[rt]*c%MOD;
        } else {
            x[rt]=c;
        }
        return;
    }
    push_down(rt);
    int mid=(l+r)>>1;
    if (ul <= mid) {
        update(ul,ur,op,c,lson);
    }
    if (ur > mid) {
        update(ul,ur,op,c,rson);
    }
    push_up(rt);
}

ll query(int ul,int ur,int q,int l,int r,int rt){
    if (ul<=l && r<=ur && flag[rt]){
        ll sum=1;
        for (int i = 0; i < q; ++i) {
            sum=sum%MOD*x[rt]%MOD;
        }
        sum=sum*(r-l+1)%MOD;
        return sum;
    }
    push_down(rt);
    ll ans=0;
    int mid=(l+r)>>1;
    if (ul<=mid){
        ans=(ans+query(ul,ur,q,lson))%MOD;
    }
    if (ur>mid){
        ans=(ans+query(ul,ur,q,rson))%MOD;
    }
    return ans;
}

int main(){
    int n,m,op,l,r,c;
    while (~scanf("%d %d",&n,&m)){
        if (n==0 && m==0) break;
        memset(x,0, sizeof(x));
        memset(flag,1, sizeof(flag));
        while (m--){
            scanf("%d %d %d %d",&op,&l,&r,&c);
//            cout<<"m:"<<m<<endl;
//            cout<<op<<","<<l<<","<<r<<","<<c<<endl;
            if (op==4){
                printf("%d\n", query(l,r,c,1,n,1));
            } else{
                update(l,r,op,c,1,n,1);
            }
        }
    }
    return 0;
}