K - Transformation

HDU - 4578

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define p 10007

#define MAXN 100010

using namespace std;

int n,m;

struct nond{

    int l,r;

    int sum[];

    int flag1,flag2,flag3;

}tree[MAXN*];

void up(int now){

    tree[now].sum[]=(tree[now*].sum[]+tree[now*+].sum[])%p;

    tree[now].sum[]=(tree[now*].sum[]+tree[now*+].sum[])%p;

    tree[now].sum[]=(tree[now*].sum[]+tree[now*+].sum[])%p;

}

void build(int now,int l,int r){

    tree[now].l=l;tree[now].r=r;

    tree[now].sum[]=;tree[now].sum[]=;

    tree[now].sum[]=;tree[now].flag2=;

    tree[now].flag1=tree[now].flag3=;

    if(tree[now].l==tree[now].r)    return ;

    int mid=(tree[now].l+tree[now].r)/;

    build(now*,l,mid);

    build(now*+,mid+,r);

    up(now);

}

void down(int now){

    if(tree[now].flag3){

        tree[now*].sum[]=(((tree[now*].r-tree[now*].l+)%p)*tree[now].flag3)%p;

        tree[now*].sum[]=(((((tree[now*].r-tree[now*].l+)%p)*tree[now].flag3)%p)*tree[now].flag3)%p;

        tree[now*].sum[]=(((((((tree[now*].r-tree[now*].l+)%p)*tree[now].flag3)%p)*tree[now].flag3)%p)*tree[now].flag3)%p;

        tree[now*].flag3=tree[now].flag3%p;

        tree[now*].flag1=;tree[now*].flag2=;

        tree[now*+].sum[]=(((tree[now*+].r-tree[now*+].l+)%p)*tree[now].flag3)%p;

        tree[now*+].sum[]=(((((tree[now*+].r-tree[now*+].l+)%p)*tree[now].flag3)%p)*tree[now].flag3)%p;

        tree[now*+].sum[]=(((((((tree[now*+].r-tree[now*+].l+)%p)*tree[now].flag3)%p)*tree[now].flag3)%p)*tree[now].flag3)%p;

        tree[now*+].flag3=tree[now].flag3%p;

        tree[now*+].flag1=;tree[now*+].flag2=;

        tree[now].flag3=;

    }

    if(tree[now].flag2){

        tree[now*].sum[]=(((((tree[now*].sum[]*tree[now].flag2)%p)*tree[now].flag2)%p)*tree[now].flag2)%p;

        tree[now*].sum[]=(((tree[now*].sum[]*tree[now].flag2)%p)*tree[now].flag2)%p;

        tree[now*].sum[]=(tree[now*].sum[]*tree[now].flag2)%p;

        tree[now*].flag1=(tree[now*].flag1*tree[now].flag2)%p;

        tree[now*].flag2=(tree[now*].flag2*tree[now].flag2)%p;

        tree[now*+].sum[]=(((((tree[now*+].sum[]*tree[now].flag2)%p)*tree[now].flag2)%p)*tree[now].flag2)%p;

        tree[now*+].sum[]=(((tree[now*+].sum[]*tree[now].flag2)%p)*tree[now].flag2)%p;

        tree[now*+].sum[]=(tree[now*+].sum[]*tree[now].flag2)%p;

        tree[now*+].flag1=(tree[now*+].flag1*tree[now].flag2)%p;

        tree[now*+].flag2=(tree[now*+].flag2*tree[now].flag2)%p;

        tree[now].flag2=;

    }

    if(tree[now].flag1){

        tree[now*].sum[]=(tree[now*].sum[]+(((*tree[now].flag1*tree[now].flag1%p*tree[now*].sum[])%p+(*tree[now].flag1*tree[now*].sum[])%p)%p+(tree[now*].r-tree[now*].l+)%p*tree[now].flag1%p*tree[now].flag1%p*tree[now].flag1)%p)%p;

        tree[now*].sum[]=(tree[now*].sum[]+((tree[now*].r-tree[now*].l+)%p*tree[now].flag1%p*tree[now].flag1%p+(*tree[now].flag1*tree[now*].sum[])%p)%p)%p;

        tree[now*].sum[]=(tree[now*].sum[]+(tree[now*].r-tree[now*].l+)%p*tree[now].flag1)%p;

        tree[now*].flag1=(tree[now*].flag1+tree[now].flag1)%p;

        tree[now*+].sum[]=(tree[now*+].sum[]+(((*tree[now].flag1*tree[now].flag1%p*tree[now*+].sum[])%p+(*tree[now].flag1*tree[now*+].sum[])%p)%p+(tree[now*+].r-tree[now*+].l+)%p*tree[now].flag1%p*tree[now].flag1%p*tree[now].flag1)%p)%p;

        tree[now*+].sum[]=(tree[now*+].sum[]+((tree[now*+].r-tree[now*+].l+)%p*tree[now].flag1%p*tree[now].flag1%p+(*tree[now].flag1*tree[now*+].sum[])%p)%p)%p;

        tree[now*+].sum[]=(tree[now*+].sum[]+(tree[now*+].r-tree[now*+].l+)%p*tree[now].flag1)%p;

        tree[now*+].flag1=(tree[now*+].flag1+tree[now].flag1)%p;

        tree[now].flag1=;

    }

}

void changeadd(int now,int l,int r,int k){

     if(tree[now].l==l&&tree[now].r==r){

        tree[now].sum[]=(tree[now].sum[]+(((*k*k%p*tree[now].sum[])%p+(*k*tree[now].sum[])%p)%p+(tree[now].r-tree[now].l+)%p*k%p*k%p*k)%p)%p;

        tree[now].sum[]=(tree[now].sum[]+(((((tree[now].r-tree[now].l+)%p)*k)%p*k)%p+(*k*tree[now].sum[])%p)%p)%p;

        tree[now].sum[]=(tree[now].sum[]+(tree[now].r-tree[now].l+)%p*k)%p;

        tree[now].flag1=(tree[now].flag1+k)%p;

        return ;

    }

    if(tree[now].flag1||tree[now].flag2!=||tree[now].flag3)    down(now);

    int mid=(tree[now].l+tree[now].r)/;

    if(r<=mid)    changeadd(now*,l,r,k);

    else if(l>mid)    changeadd(now*+,l,r,k);

    else { changeadd(now*,l,mid,k); changeadd(now*+,mid+,r,k); }

    up(now);

}

void changemul(int now,int l,int r,int k){

    if(tree[now].l==l&&tree[now].r==r){

        tree[now].sum[]=(((((tree[now].sum[]*k)%p)*k)%p)*k)%p;

        tree[now].sum[]=(((tree[now].sum[]*k)%p)*k)%p;

        tree[now].sum[]=(tree[now].sum[]*k)%p;

        tree[now].flag1=(tree[now].flag1*k)%p;

        tree[now].flag2=(tree[now].flag2*k)%p;

        return ;

    }

    if(tree[now].flag1||tree[now].flag2!=||tree[now].flag3)    down(now);

    int mid=(tree[now].l+tree[now].r)/;

    if(r<=mid)    changemul(now*,l,r,k);

    else if(l>mid)    changemul(now*+,l,r,k);

    else{ changemul(now*,l,mid,k); changemul(now*+,mid+,r,k); }

    up(now);

}

void change(int now,int l,int r,int k){

    if(tree[now].l==l&&tree[now].r==r){

        tree[now].sum[]=(((tree[now].r-tree[now].l+)%p)*k)%p;

        tree[now].sum[]=(((((tree[now].r-tree[now].l+)%p)*k)%p)*k)%p;

        tree[now].sum[]=(((((((tree[now].r-tree[now].l+)%p)*k)%p)*k)%p)*k)%p;

        tree[now].flag3=k%p;

        tree[now].flag1=;tree[now].flag2=;

        return ;

    }

    if(tree[now].flag1||tree[now].flag2!=||tree[now].flag3)    down(now);

    int mid=(tree[now].l+tree[now].r)/;

    if(r<=mid)    change(now*,l,r,k);

    else if(l>mid)    change(now*+,l,r,k);

    else{ change(now*,l,mid,k); change(now*+,mid+,r,k); }

    up(now);

}

int query(int now,int l,int r,int k){

    if(tree[now].l==l&&tree[now].r==r)

        return tree[now].sum[k];

    if(tree[now].flag1||tree[now].flag2!=||tree[now].flag3)    down(now);

    int mid=(tree[now].l+tree[now].r)/;

    if(r<=mid)    return query(now*,l,r,k);

    else if(l>mid)    return query(now*+,l,r,k);

    else return (query(now*,l,mid,k)+query(now*+,mid+,r,k))%p;

}

int main(){

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

        build(,,n);

        for(int i=;i<=m;i++){

            int a,b,c,d;

            scanf("%d%d%d%d",&a,&b,&c,&d);

            if(a==)    changeadd(,b,c,d);

            if(a==)    changemul(,b,c,d);

            if(a==)    change(,b,c,d);

            if(a==)    printf("%d\n",query(,b,c,d));

        }

    }

}