无需看的前情

好吧是这样的有人把 Ynoi rprmq2 搬到了校内赛上，目前全机房最快的代码，在那题（数据为五万）需要 4.3s。

时限因为校内老爷机可视作为 2s，据推算标程本地用时大约为 0.8s~1s.

求教万能的谷民一些数据结构卡常技巧。

看不懂也随便提点建议也好哇。

#include<set>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define uni unsigned
#define ll long long
#define getrk(x,y,z) lower_bound(y,y+z,x)-y
using namespace std;
const int N=50010,B0=800,FSIZE=1<<23;
uni m,dx[N],dy[N],lex,ley;
ll b[B0][B0],mx[B0][B0];
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF,st[11],*c=st;
template<typename T>void read(T &x){
    for(;48>*InF||*InF>57;++InF);
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
}
void write(ll x){
    if(!x) *OnF++=48;
    for(;x;*++c=x%10^48,x/=10);
    for(;c!=st;*OnF++=*c--);
    *OnF++='\n';
}
void cmax(ll &x,ll y){if(x<y) x=y;}
struct ques{
    uni x,y;
    int z00,z01,z10,z11;
    bool operator<(ques b)const{return(x<b.x);}
    void get(){
        read(x);read(y);read(z00);read(z01);read(z10);read(z11);
    }
}q[N];
struct ST{    // 线段树，支持区间加，区间历史最值，历史最值回滚
    struct node{
        uni mid;
        ll add,mx,_add,_mx;
        bool ret;
    }a[N<<7];
    void _add(node &x,ll y,ll z){
        cmax(x._add,x.add+z);
        cmax(x._mx,x.mx+z);
        x.add+=y;
        x.mx+=y;
    }
    void reset(uni x=1){
        node &w=a[x];
        _add(a[x<<1],w.add,w._add);
        _add(a[x<<1|1],w.add,w._add);
        w.add=w._add=0;
        w._mx=w.mx;
        w.ret=1;
    }
    void pushdown(uni x){
        node &w=a[x];
        if(w.ret){
            reset(x<<1);
            reset(x<<1|1);
            w.ret=0;
        }
        if(w.add||w._add){
            _add(a[x<<1],w.add,w._add);
            _add(a[x<<1|1],w.add,w._add);
            w.add=w._add=0;
        }
    }
    void build(uni bl,uni br,uni p=1,uni l=1,uni r=m){
        a[p]=node();
        if(l==r) return;
        if(bl==br){
            a[p].mid=(l+r)>>1;
            build(bl,br,p<<1,l,a[p].mid);
            return(build(bl,br,p<<1|1,a[p].mid+1,r));
        }
        uni bd=(bl+br)>>1; 
        a[p].mid=dy[bd+1]-1;
        build(bl,bd,p<<1,l,a[p].mid);
        build(bd+1,br,p<<1|1,a[p].mid+1,r);
    }
    void push(uni bl,uni br,ll *s,uni p=1){
        if(bl==br){
            s[bl]=a[p]._mx;
            return;
        }
        pushdown(p);
        push(bl,(bl+br)>>1,s,p<<1);
        push(((bl+br)>>1)+1,br,s,p<<1|1);
    }
    void modify(uni x,int y,int z,uni p=1,uni l=1,uni r=m){
        pushdown(p);
        if(x<=a[p].mid) modify(x,y,z,p<<1,l,a[p].mid);
        else _add(a[p<<1],y,y);
        if(x>a[p].mid+1) modify(x,y,z,p<<1|1,a[p].mid+1,r);
        else _add(a[p<<1|1],z,z);
        a[p].mx=max(a[p<<1].mx,a[p<<1|1].mx);
        a[p]._mx=max(a[p<<1]._mx,a[p<<1|1]._mx);
    }
}t;
struct ST2{    // 四分树，支持子矩阵加，子矩阵最大值
    struct node{
        ll mx,add;
        uni s0,s1,s2,s3;
    }a[N<<5];
    ll ans0,ans1,ans2,ans3;
    uni size,x,y;
    int z0,z1,z2,z3;
    void build(uni p=1,uni l0=0,uni r0=lex,uni l1=0,uni r1=ley){
        a[p]=node();
        if(l0==r0&&l1==r1){
            a[p].mx=b[l0][l1];
            return;
        }
        uni mdx=(l0+r0)>>1,mdy=(l1+r1)>>1;
        build(a[p].s0=++size,l0,mdx,l1,mdy);
        if(l1!=r1) build(a[p].s1=++size,l0,mdx,mdy+1,r1);
        if(l0!=r0){
            build(a[p].s2=++size,mdx+1,r0,l1,mdy);
            if(l1!=r1) build(a[p].s3=++size,mdx+1,r0,mdy+1,r1);
        }
        a[p].mx=max(max(a[a[p].s0].mx,a[a[p].s1].mx),max(a[a[p].s2].mx,a[a[p].s3].mx));
    }
    void _add(node &x,int z){
        x.mx+=z;
        x.add+=z;
    }
    void get(uni p=1,uni l0=0,uni r0=lex,uni l1=0,uni r1=ley,ll up=0){
        node &w=a[p];
        if(r0<x&&r1<y){
            cmax(ans0,w.mx+up);
            return(_add(w,z0));
        }
        if(r0<x&&y<=l1){
            cmax(ans1,w.mx+up);
            return(_add(w,z1));
        }
        if(x<=l0&&r1<y){
            cmax(ans2,w.mx+up);
            return(_add(w,z2));
        }
        if(x<=l0&&y<=l1){
            cmax(ans3,w.mx+up);
            return(_add(w,z3));
        }
        uni mdx=(l0+r0)>>1,mdy=(l1+r1)>>1;
        get(w.s0,l0,mdx,l1,mdy,up+=w.add);
        if(w.s1) get(w.s1,l0,mdx,mdy+1,r1,up);
        if(w.s2) get(w.s2,mdx+1,r0,l1,mdy,up);
        if(w.s3) get(w.s3,mdx+1,r0,mdy+1,r1,up);
        w.mx=max(max(a[w.s0].mx,a[w.s1].mx),max(a[w.s2].mx,a[w.s3].mx))+w.add;
    }
}bt;
#define lsh(a,b)\
    sort(a,a+end-i+1);\
    b=unique(a,a+end-i+1)-a;\
    a[b--]=m+1;
multiset<ques> qs;
void before(uni i,uni end){    // 块间贡献
    t.build(0,ley);
    memset(b,0,sizeof(b));
    for(auto &j:qs) t.modify(j.y,j.z00,j.z01);
    uni col=0;
    for(auto j=qs.begin(),k=j;j!=qs.end();){
        for(;j->x>dx[col+1];t.reset()) t.push(0,ley,b[col++]);
        for(;k!=qs.end()&&j->x==k->x;++k) t.modify(k->y,-k->z00,-k->z01);
        for(;j->x>=dx[col+1]&&col<=lex;t.reset()) t.push(0,ley,b[col++]);
        for(;j!=k;++j) t.modify(j->y,j->z10,j->z11);
    }
    if(col<=lex){
        t.push(0,ley,b[col++]);
        t.reset();
        for(;col<=lex;t.push(0,ley,b[col++]));
    }
}
void after(uni i,uni end){    // 块内贡献
    bt.size=1;
    bt.build();
    for(uni j=i;j<end;++j){
        qs.insert(q[j]);
        bt.x=getrk(q[j].x,dx,lex);bt.y=getrk(q[j].y,dy,ley);
        bt.z0=q[j].z00;bt.z1=q[j].z01;
        bt.z2=q[j].z10;bt.z3=q[j].z11;
        bt.ans0=bt.ans1=bt.ans2=bt.ans3=0;
        bt.get();
        write(bt.ans0);write(bt.ans1);
        write(bt.ans2);write(bt.ans3);
    }
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(m);
    const uni BSIZE=sqrt(m*6);
    for(uni i=0;i<m;++i) q[i].get();
    for(uni i=0,end;i<m;i=end){
        end=min(m,i+BSIZE);
        dx[0]=dy[0]=1;
        for(uni j=i;j<end;++j){
            dx[j-i+1]=q[j].x;
            dy[j-i+1]=q[j].y;
        }
        lsh(dx,lex);
        lsh(dy,ley);
        before(i,end);
        after(i,end);
    }
    fwrite(WuF,1,OnF-WuF,stdout);
    fclose(stdin);
    fclose(stdout);
    return(0);
}