卡常的kdtree……将标识符看为y轴上的对应的点，然后直接在kdtree上标记就可以了
被卡常了很悲伤……以下代码目前没有卡常卡过去先放着吧
------
UPD 2016.9.29
找管理员要来了数据……本机是9s不到(开O2)17s(不开O2)，到了bzoj上就是20s+……
我从14s+卡常卡到9s不到容易吗我……
就不能放宽点时限么……
没错我现在还是TLE
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define Add(x,y) (x=(x+y)%P)
#define Mul(x,y) (x=x*y%P)
const int N=50005;
const long long P=536870912ll;
int n,m,sort_tag,root,l,r;
long long x,y;
template<typename T>inline void Read(T &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}
struct KDTree{
int d[2],mn[2],mx[2],ch[2];
long long add,mul,sum,v,siz;
KDTree(){mul=siz=1;sum=v=add=0;}
friend inline bool operator<(const KDTree &A,const KDTree &B){return A.d[sort_tag]<B.d[sort_tag];}
}tree[N];
inline void Pushdown(int rt){
if(tree[rt].mul!=1){
if(tree[rt].ch[0]){
Mul(tree[tree[rt].ch[0]].add,tree[rt].mul);
Mul(tree[tree[rt].ch[0]].sum,tree[rt].mul);
Mul(tree[tree[rt].ch[0]].mul,tree[rt].mul);
Mul(tree[tree[rt].ch[0]].v,tree[rt].mul);
}
if(tree[rt].ch[1]){
Mul(tree[tree[rt].ch[1]].add,tree[rt].mul);
Mul(tree[tree[rt].ch[1]].sum,tree[rt].mul);
Mul(tree[tree[rt].ch[1]].mul,tree[rt].mul);
Mul(tree[tree[rt].ch[1]].v,tree[rt].mul);
}
tree[rt].mul=1;
}
if(tree[rt].add){
if(tree[rt].ch[0]){
Add(tree[tree[rt].ch[0]].add,tree[rt].add);
Add(tree[tree[rt].ch[0]].sum,tree[rt].add*tree[tree[rt].ch[0]].siz%P);
Add(tree[tree[rt].ch[0]].v,tree[rt].add);
}
if(tree[rt].ch[1]){
Add(tree[tree[rt].ch[1]].add,tree[rt].add);
Add(tree[tree[rt].ch[1]].sum,tree[rt].add*tree[tree[rt].ch[1]].siz%P);
Add(tree[tree[rt].ch[1]].v,tree[rt].add);
}
tree[rt].add=0;
}
}
inline void Pushup_(int rt){
tree[rt].sum=tree[rt].siz=0;
if(tree[rt].ch[0]){
tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[0]].mx[0]);
tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[0]].mx[1]);
tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[0]].mn[0]);
tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[0]].mn[1]);
Add(tree[rt].siz,tree[tree[rt].ch[0]].siz);
Add(tree[rt].sum,tree[tree[rt].ch[0]].sum);
}
if(tree[rt].ch[1]){
tree[rt].mx[0]=max(tree[rt].mx[0],tree[tree[rt].ch[1]].mx[0]);
tree[rt].mx[1]=max(tree[rt].mx[1],tree[tree[rt].ch[1]].mx[1]);
tree[rt].mn[0]=min(tree[rt].mn[0],tree[tree[rt].ch[1]].mn[0]);
tree[rt].mn[1]=min(tree[rt].mn[1],tree[tree[rt].ch[1]].mn[1]);
Add(tree[rt].siz,tree[tree[rt].ch[1]].siz);
Add(tree[rt].sum,tree[tree[rt].ch[1]].sum);
}
Add(tree[rt].sum,tree[rt].v);
Add(tree[rt].siz,1ll);
}
int Build(int l,int r,int t){
int mid=l+r>>1;
sort_tag=t;
nth_element(tree+l,tree+mid,tree+r+1);
tree[mid].mn[0]=tree[mid].mx[0]=tree[mid].d[0];
tree[mid].mn[1]=tree[mid].mx[1]=tree[mid].d[1];
if(l<mid)tree[mid].ch[0]=Build(l,mid-1,t^1);
if(r>mid)tree[mid].ch[1]=Build(mid+1,r,t^1);
Pushup_(mid);
return mid;
}
void Addv(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(!tag){
if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
Mul(tree[rt].sum,x);
Add(tree[rt].sum,y*tree[rt].siz%P);
Mul(tree[rt].mul,x);
Mul(tree[rt].add,x);
Add(tree[rt].add,y);
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
return;
}
if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
long long vx=tree[rt].v;
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
Add(tree[rt].sum,tree[rt].v-vx);
}
int mid=tree[rt].d[tag];
if(l<mid)Addv(tree[rt].ch[0],tag^1);
if(r>mid)Addv(tree[rt].ch[1],tag^1);
tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
Mul(tree[rt].sum,x);
Add(tree[rt].sum,y*tree[rt].siz%P);
Mul(tree[rt].mul,x);
Mul(tree[rt].add,x);
Add(tree[rt].add,y);
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
return;
}
if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
long long vx=tree[rt].v;
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
Add(tree[rt].sum,tree[rt].v-vx);
}
if(l<=tree[rt].mx[!tag])Addv(tree[rt].ch[0],tag^1);
if(r>=tree[rt].mn[!tag])Addv(tree[rt].ch[1],tag^1);
tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}
void Addv2(int rt,int tag){
if(!rt)return;
Pushdown(rt);
if(tag){
if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r){
Mul(tree[rt].sum,x);
Add(tree[rt].sum,y*tree[rt].siz%P);
Mul(tree[rt].mul,x);
Mul(tree[rt].add,x);
Add(tree[rt].add,y);
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
return;
}
if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r){
long long vx=tree[rt].v;
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
Add(tree[rt].sum,tree[rt].v-vx);
}
int mid=tree[rt].d[tag];
if(l<mid)Addv2(tree[rt].ch[0],tag^1);
if(r>mid)Addv2(tree[rt].ch[1],tag^1);
tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
else {
if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r){
Mul(tree[rt].sum,x);
Add(tree[rt].sum,y*tree[rt].siz%P);
Mul(tree[rt].mul,x);
Mul(tree[rt].add,x);
Add(tree[rt].add,y);
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
return;
}
if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r){
long long vx=tree[rt].v;
Mul(tree[rt].v,x);
Add(tree[rt].v,y);
Add(tree[rt].sum,tree[rt].v-vx);
}
if(l<=tree[rt].mx[!tag])Addv2(tree[rt].ch[0],tag^1);
if(r>=tree[rt].mn[!tag])Addv2(tree[rt].ch[1],tag^1);
tree[rt].sum=(tree[tree[rt].ch[0]].sum+tree[tree[rt].ch[1]].sum+tree[rt].v)%P;
}
}
long long Sum(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(!tag){
if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
int mid=tree[rt].d[tag];
if(l<mid)ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
if(r>mid)ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
return ans;
}
else {
if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
if(l<=tree[rt].mx[!tag])ans=(ans+Sum(tree[rt].ch[0],!tag))%P;
if(r>=tree[rt].mn[!tag])ans=(ans+Sum(tree[rt].ch[1],!tag))%P;
return ans;
}
}
long long Sum2(int rt,int tag){
if(!rt)return 0ll;
long long ans=0ll;
Pushdown(rt);
if(tag){
if(l<=tree[rt].mn[tag] && tree[rt].mx[tag]<=r)return tree[rt].sum;
if(l<=tree[rt].d[tag] && tree[rt].d[tag]<=r)ans=(ans+tree[rt].v)%P;
int mid=tree[rt].d[tag];
if(l<mid)ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
if(r>mid)ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
return ans;
}
else {
if(l<=tree[rt].mn[!tag] && tree[rt].mx[!tag]<=r)return tree[rt].sum;
if(l<=tree[rt].d[!tag] && tree[rt].d[!tag]<=r)ans=(ans+tree[rt].v)%P;
if(l<=tree[rt].mx[!tag])ans=(ans+Sum2(tree[rt].ch[0],!tag))%P;
if(r>=tree[rt].mn[!tag])ans=(ans+Sum2(tree[rt].ch[1],!tag))%P;
return ans;
}
}
int main(){
freopen("4303.in","r",stdin);
freopen("4303.out","w",stdout);
Read(n);Read(m);
for(register int i=1;i<=n;i++){Read(tree[i].d[1]);tree[i].d[0]=i;}
root=Build(1,n,1);
while(m--){
static int opt;
Read(opt);Read(l);Read(r);
if(opt==0){Read(x);Read(y);Addv(root,1);}
if(opt==1){Read(x);Read(y);Addv2(root,1);}
if(opt==2){printf("%lld\n",Sum(root,1));}
if(opt==3){printf("%lld\n",Sum2(root,1));}
}
return 0;
}
评论 (0)
