hdoj 4578 라인 트리

/////////////////////////////////////////////////////////////////////////
// File Name: 4578.cpp
// Author: wang
// mail: 
// Created Time: 2013-8-11 15:19:21
/////////////////////////////////////////////////////////////////////////
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <cmath>

#include <algorithm>
#include<iostream>
#include<queue>
#include <map>
using namespace std;
typedef long long ll;
#define INF (INT_MAX/10)
#define SQR(x) ((x)*(x))
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repf(i, a, b) for (int i=(a); i<=(b); ++i)
#define repd(i, a, b) for (int i=(a); i>=(b); --i)
#define clr(ar,val) memset(ar, val, sizeof(ar))
#define N 100100
#define mod 10007
int n,m;

struct node
{
	int add,mul;
	int sum[3];
	int l,r;
	void _mul(int c)
	{
	    sum[0]=sum[0]*c%mod;
		sum[1]=sum[1]*c%mod*c%mod;
		sum[2]=sum[2]*c%mod*c%mod*c%mod;
        mul=mul*c%mod;
		add=add*c%mod;
	}
    void _add(int c)
	{
		int len=r-l+1;
	    sum[2]=(sum[2]+3*sum[1]%mod*c)%mod;
		sum[2]+=3*sum[0]%mod*c%mod*c%mod;
		sum[2]=(sum[2]%mod+len*c%mod*c%mod*c%mod)%mod;

		sum[1]=(sum[1]+len*c%mod*c%mod)%mod;
		sum[1]=(sum[1]+2*sum[0]*c)%mod;
		sum[0]=(sum[0]+len*c)%mod;
		add=(add+c)%mod;
	}
};
node a[N*20];
void fun(int s)
{
	a[2*s]._mul(a[s].mul);
	a[2*s+1]._mul(a[s].mul);
	a[2*s]._add(a[s].add);
	a[2*s+1]._add(a[s].add);
	a[s].mul=1;
	a[s].add=0;
}
void update(int s,int l,int r,int mul,int add)
{
	if(l<=a[s].l && r>=a[s].r)
	{
		a[s]._mul(mul);
		a[s]._add(add);
		return ;
	}
	fun(s);
	int mid=(a[s].l+a[s].r)/2;
	if(l>mid) update(2*s+1,l,r,mul,add);
	else if(r<=mid) update(2*s,l,r,mul,add);
	else
	{
		update(2*s,l,r,mul,add);
		update(2*s+1,l,r,mul,add);
	}
	rep(i,3)
		a[s].sum[i]=(a[s*2].sum[i]+a[2*s+1].sum[i])%mod;
}
int query(int s,int l,int r,int c)
{
	if(l<=a[s].l && r>=a[s].r)
	{
		return a[s].sum[c];
	}
	fun(s);
	int mid=(a[s].l+a[s].r)/2;
	if(l>mid) return query(2*s+1,l,r,c);
	else if(r<=mid) return query(2*s,l,r,c);
	else return (query(2*s,l,r,c)+query(2*s+1,l,r,c))%mod;
}
void maketree(int s,int l,int r)
{
	a[s].l=l; a[s].r=r;
	rep(i,3) a[s].sum[i]=0;
	a[s].mul=1; a[s].add=0;
	if(l==r) return ;
	int mid=(a[s].l+a[s].r)/2;
	maketree(2*s,l,mid);
	maketree(2*s+1,mid+1,r);
}
int main()
{
	while(scanf("%d%d",&m,&n))
	{
		if(n==0 && m==0) break;
		maketree(1,1,n);
		int x,y,sign,c;
		rep(i,m)
		{
			scanf("%d%d%d%d",&sign,&x,&y,&c);
			if(sign==1)
				update(1,x,y,1,c);
			else if(sign==2)
				update(1,x,y,c,0);
			else if(sign==3)
				update(1,x,y,0,c);
			else
				printf("%d
",query(1,x,y,c-1));
		}
	}
}