题目大意:
Transformation
思路:
AC Code:
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
#define INF 0x3f3f3f3f
const int M=10007;
const int N=1e5 +9;
int n, m , c, x, y, v;
struct segtree{
int s1, s2, s3;
int lazya, lazym, lazyc;
void clear(){
s1=s2=s3=0;
lazya=lazyc=0;
lazym=1;
}
}tr[N<<2];
inline int lc(int p) {return p<<1;}
inline int rc(int p) {return p<<1|1;}
inline void push_up(int p){
tr[p].s1=(tr[lc(p)].s1+tr[rc(p)].s1)%M;
tr[p].s2=(tr[lc(p)].s2+tr[rc(p)].s2)%M;
tr[p].s3=(tr[lc(p)].s3+tr[rc(p)].s3)%M;
}
inline void build(int p, int l, int r){
tr[p].clear();
if(l==r) return ;
int mid=(l+r)>>1;
build(lc(p), l, mid);
build(rc(p), mid+1, r);
}
inline void f(int f, int p, int len){
int k;
if(tr[f].lazyc){
k=tr[f].lazyc;
tr[p].s3=len*k*k*k%M;
tr[p].s2=len*k*k%M;
tr[p].s1=len*k%M;
tr[p].lazya=0;
tr[p].lazym=1;
tr[p].lazyc=k;
}
if(tr[f].lazym!=1){
k=tr[f].lazym;
tr[p].s3=k*k*k*tr[p].s3%M;
tr[p].s2=k*k*tr[p].s2%M;
tr[p].s1=k*tr[p].s1%M;
tr[p].lazya=k*tr[p].lazya%M;
tr[p].lazym=k*tr[p].lazym%M;
}
if(tr[f].lazya){
k=tr[f].lazya;
tr[p].s3=(tr[p].s3 + len*k*k*k + 3*k*tr[p].s2 + 3*k*k*tr[p].s1)%M;
tr[p].s2=(tr[p].s2 + len*k*k + 2*k*tr[p].s1)%M;
tr[p].s1=(tr[p].s1 + len*k)%M;
tr[p].lazya=(tr[p].lazya + k)%M;
}
}
inline void push_down(int p, int lenl, int lenr){
f(p, lc(p), lenl);
f(p, rc(p), lenr);
tr[p].lazya=tr[p].lazyc=0;
tr[p].lazym=1;
}
inline void updata(int p, int l, int r, int x, int y, int k){
if(l<=x && y<=r){
int len=y-x+1;
if(c==1){
tr[p].lazya=(tr[p].lazya+k)%M;
tr[p].s3=(tr[p].s3 + len*k*k*k + 3*k*tr[p].s2 + 3*k*k*tr[p].s1)%M;
tr[p].s2=(tr[p].s2 + 2*k*tr[p].s1 + len*k*k)%M;
tr[p].s1=(tr[p].s1 + len*k)%M;
}
else if(c==2){
tr[p].lazya=tr[p].lazya*k%M;
tr[p].lazym=tr[p].lazym*k%M;
tr[p].s3=k*k*k*tr[p].s3%M;
tr[p].s2=k*k*tr[p].s2%M;
tr[p].s1=k*tr[p].s1%M;
}
else{
tr[p].lazyc=k;
tr[p].lazya=0;
tr[p].lazym=1;
tr[p].s3=len*k*k*k%M;
tr[p].s2=len*k*k%M;
tr[p].s1=len*k%M;
}
return ;
}
int mid=(x+y)>>1;
push_down(p, mid-x+1, y-mid);
if(l<=mid) updata(lc(p), l, r, x, mid, k);
if(r>mid) updata(rc(p), l, r, mid+1, y, k);
push_up(p);
}
inline int query(int p, int l, int r, int x, int y){
if(l<=x && y<=r){
if(v==1) return tr[p].s1;
else if(v==2) return tr[p].s2;
else return tr[p].s3;
}
int mid=(x+y)>>1;
push_down(p, mid-x+1, y-mid);
int ans=0;
if(l<=mid) ans=(ans+query(lc(p), l, r, x, mid))%M;
if(r>mid) ans=(ans+query(rc(p), l, r, mid+1, y))%M;
return ans;
}
signed main(){
while(~scanf("%lld%lld", &n, &m)&&(n||m)){
build(1,1,n);
for(int i=1; i<=m; i++){
scanf("%lld%lld%lld%lld", &c, &x, &y, &v);
if(c==4) printf("%lld\n", query(1,x,y,1,n));
else updata(1,x,y,1,n,v);
}
}
return 0;
}
Comments | NOTHING