按书上思路写了三个小时才发现书上思路是错的，现在要在现代码上修改甚至不如换思路重写，最痛苦的一集
还差一点点优化就能AC的TLE代码：
#include<iostream>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll a[N]={0};
ll tree[N<<2],sum2[N<<2],sum3[N<<2];
ll mod=10007;
struct t
{
int add,mul;
bool dif;
}tag[N<<2];
inline ll ls(ll p){return p<<1;}
inline ll rs(ll p){return p<<1|1;}
void push_up(ll p)
{
tree[p]=(tree[ls(p)]+tree[rs(p)])%mod;
sum2[p]=(sum2[ls(p)]+sum2[rs(p)])%mod;
sum3[p]=(sum3[ls(p)]+sum3[rs(p)])%mod;
}
void build(ll p,ll pl,ll pr)
{
tag[p].add=0;tag[p].mul=1;
tag[p].dif=true;
if(pl==pr)
{
tree[p]=sum2[p]=sum3[p]=0;
return;
}
ll mid=(pl+pr)>>1;
build(ls(p),pl,mid);
build(rs(p),mid+1,pr);
}
void addtag_add(ll p,ll pl,ll pr,ll d)
{
tag[p].add=(tag[p].add+d)%mod;
sum3[p]=(sum3[p]+d*d*d*(pr-pl+1)%mod+3*d*sum2[p]%mod+3*d*d*tree[p]%mod)%mod;
sum2[p]=(sum2[p]+(pr-pl+1)*d*d%mod+2*tree[p]*d%mod)%mod;
tree[p]=(tree[p]+d*(pr-pl+1)%mod)%mod;
}
void addtag_mul(ll p,ll pl,ll pr,ll d)
{
tag[p].mul=tag[p].mul*d%mod;
tag[p].add=d*tag[p].add%mod;
tree[p]=d*tree[p]%mod;
sum2[p]=d*d*sum2[p]%mod;
sum3[p]=d*d*d%mod*sum3[p]%mod;
}
void push_down(ll p,ll pl,ll pr)
{
ll mid=(pl+pr)>>1;
addtag_mul(ls(p),pl,mid,tag[p].mul);
addtag_mul(rs(p),mid+1,pr,tag[p].mul);
addtag_add(ls(p),pl,mid,tag[p].add);
addtag_add(rs(p),mid+1,pr,tag[p].add);
tag[p].mul=1;tag[p].add=0;
tag[p].dif=false;
tag[ls(p)].dif=tag[rs(p)].dif=true;
}
void update_add(ll L,ll R,ll p,ll pl,ll pr,ll d)
{
if(L<=pl&&pr<=R)
{
addtag_add(p,pl,pr,d);
return;
}
push_down(p,pl,pr);
ll mid=(pl+pr)>>1;
if(L<=mid)
update_add(L,R,ls(p),pl,mid,d);
if(R>mid)
update_add(L,R,rs(p),mid+1,pr,d);
push_up(p);
}
void update_mul(ll L,ll R,ll p,ll pl,ll pr,ll d)
{
if(L<=pl&&pr<=R)
{
addtag_mul(p,pl,pr,d);
return;
}
push_down(p,pl,pr);
ll mid=(pl+pr)>>1;
if(L<=mid)
update_mul(L,R,ls(p),pl,mid,d);
if(R>mid)
update_mul(L,R,rs(p),mid+1,pr,d);
push_up(p);
}
void update_change(ll L,ll R,ll p,ll pl,ll pr,ll c)
{
if(pl==pr)
{
tree[p]=c;sum2[p]=c*c%mod;sum3[p]=c*c*c%mod;
tag[p].add=0;tag[p].mul=1;
return;
}
if(L<=pl&&pr<=R)
{
tree[p]=c*(pr-pl+1)%mod;
sum2[p]=c*c*(pr-pl+1)%mod;
sum3[p]=c*c*c%mod*(pr-pl+1)%mod;
}
ll mid=(pl+pr)>>1;
if(L<=mid)
update_change(L,R,ls(p),pl,mid,c);
if(R>mid)
update_change(L,R,rs(p),mid+1,pr,c);
push_up(p);
}
ll query(ll L,ll R,ll p,ll pl,ll pr)
{
if(L<=pl&&pr<=R)
return tree[p];
push_down(p,pl,pr);
ll ans=0;
ll mid=(pl+pr)>>1;
if(L<=mid)
ans+=query(L,R,ls(p),pl,mid)%mod;
if(R>mid)
ans+=query(L,R,rs(p),mid+1,pr)%mod;
return ans%mod;
}
ll query2(ll L,ll R,ll p,ll pl,ll pr)
{
if(L<=pl&&pr<=R)
return sum2[p];
push_down(p,pl,pr);
ll ans=0;
ll mid=(pl+pr)>>1;
if(L<=mid)
ans+=query2(L,R,ls(p),pl,mid)%mod;
if(R>mid)
ans+=query2(L,R,rs(p),mid+1,pr)%mod;
return ans%mod;
}
ll query3(ll L,ll R,ll p,ll pl,ll pr)
{
if(L<=pl&&pr<=R)
return sum3[p];
push_down(p,pl,pr);
ll ans=0;
ll mid=(pl+pr)>>1;
if(L<=mid)
ans+=query3(L,R,ls(p),pl,mid)%mod;
if(R>mid)
ans+=query3(L,R,rs(p),mid+1,pr)%mod;
return ans%mod;
}
// void dfs(ll p,ll pl,ll pr)
// {
// if(pl==pr)
// {
// cout<<tree[p]<<' ';
// return;
// }
// ll mid=(pl+pr)>>1;
// dfs(ls(p),pl,mid);
// dfs(rs(p),mid+1,pr);
// }
int main() {
ios::sync_with_stdio(false);
int n,m;
while(scanf("%d %d",&n,&m))
{
if(n==0&&m==0)
break;
build(1,1,n);
while(m--)
{
int op,l,r,x;
scanf("%d %d %d %d",&op,&l,&r,&x);
if(op==1)
update_add(l,r,1,1,n,x);
else if(op==2)
update_mul(l,r,1,1,n,x);
else if(op==3)
update_change(l,r,1,1,n,x);
else if(op==4)
{
if(x==1)
cout<<query(l,r,1,1,n)%mod<<'\n';
else if(x==2)
cout<<query2(l,r,1,1,n)%mod<<'\n';
else if(x==3)
cout<<query3(l,r,1,1,n)%mod<<'\n';
}
// dfs(1,1,n);
// cout<<'\n';
}
}
return 0;
}