程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 4578 Transformation

hdu 4578 Transformation

編輯：C++入門知識

hdu 4578 Transformation

又做了一道好題。。

有三種操作：

1 a b c [a,b]加上c

2 a b c [a,b]乘上c

3 a b c [a,b]變為c

4 a b c 求[a,b]的c次方和(1<=c<=3)

這題首先需要解決的第一個問題是加上或乘上一個數對這個區間的c次方和分別產生什麼改變，很簡單，一化簡就能得到。

第二個問題是當一段區間上既有乘又有加的lazy時應該怎麼向下推送，因為一段區間上只能有一個lazy，我起初做的是先將有lazy的標記向下傳，直到不沖突為止，然後更新這個區間的lazy，後來無數次的wa。代碼太長了，簡直無法debug。

同學說要找到這兩個lazy的關系，即可以把每個數看做mult * x + add。加上一個數y時,add+= y，乘上一個數y時，mult *= y，add *= y。這樣就解決了先加後乘和先乘後加的問題了，感覺好機智，mark。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL long long
#define LL __int64
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 100010;
const int mod = 10007;

struct node
{
    int l,r;
    int mult,add;
    int s[4];
} tree[maxn*4];


void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].mult = 1;
	tree[v].add = 0;
	tree[v].s[1] = tree[v].s[2] = tree[v].s[3] = 0;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}
void cal(int v,int mult, int add)
{
	int len = tree[v].r - tree[v].l + 1;

	tree[v].s[1] = tree[v].s[1] * mult%mod;
	tree[v].s[2] = tree[v].s[2] * mult%mod*mult%mod;
	tree[v].s[3] = tree[v].s[3] * mult%mod*mult%mod*mult%mod;
	tree[v].mult = (tree[v].mult * mult)%mod;
	tree[v].add = (tree[v].add * mult)%mod;

	tree[v].s[3] = (tree[v].s[3] + 3*add%mod*add%mod*tree[v].s[1]%mod)%mod;
	tree[v].s[3] = (tree[v].s[3] + 3*add%mod*tree[v].s[2]%mod)%mod;
	tree[v].s[3] = (tree[v].s[3] + len*add%mod*add%mod*add%mod)%mod;
	tree[v].s[2] = (tree[v].s[2] + 2*add%mod*tree[v].s[1]%mod)%mod;
	tree[v].s[2] = (tree[v].s[2] + len*add%mod*add%mod)%mod;
	tree[v].s[1] = (tree[v].s[1] + len*add%mod)%mod;
	tree[v].add = (tree[v].add + add)%mod;
}

void push_down(int v)
{
	if(tree[v].l == tree[v].r)
		return;
	cal(v*2,tree[v].mult,tree[v].add);
	cal(v*2+1,tree[v].mult,tree[v].add);
	tree[v].mult = 1;
	tree[v].add = 0;
}

void push_up(int v)
{
	int ls = v*2,rs = v*2+1;
	tree[v].s[1] = (tree[ls].s[1] + tree[rs].s[1])%mod;
	tree[v].s[2] = (tree[ls].s[2] + tree[rs].s[2])%mod;
	tree[v].s[3] = (tree[ls].s[3] + tree[rs].s[3])%mod;
}

void update(int v, int l, int r, int mult, int add)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		cal(v,mult,add);
		return;
	}

	push_down(v);

	int mid = (tree[v].l + tree[v].r) >> 1;

	if(r <= mid)
		update(v*2,l,r,mult,add);
	else if(l > mid)
		update(v*2+1,l,r,mult,add);
	else
	{
		update(v*2,l,mid,mult,add);
		update(v*2+1,mid+1,r,mult,add);
	}
	push_up(v);
}

int query(int v, int l, int r,int p)
{
	if(tree[v].l == l && tree[v].r == r)
	{
		return tree[v].s[p];
	}
	push_down(v);
	int mid = (tree[v].l + tree[v].r) >> 1;
	if(r <= mid)
		return query(v*2,l,r,p);
	else if(l > mid)
		return query(v*2+1,l,r,p);
	else
		return (query(v*2,l,mid,p) + query(v*2+1,mid+1,r,p))%mod;
}

int main()
{
    int n,m;
    int op,x,y,c;
    while(~scanf(%d %d,&n,&m))
    {
        if(n == 0 && m == 0) break;
        build(1,1,n);
        while(m--)
        {
            scanf(%d %d %d %d,&op,&x,&y,&c);
            if(op == 1)
				update(1,x,y,1,c);
			else if(op == 2)
				update(1,x,y,c,0);
			else if(op == 3)
				update(1,x,y,0,c);
            else
                printf(%d
,query(1,x,y,c)%mod);
        }
    }
    return 0;
}