2019.01.22 bzoj2874: 训练士兵（主席树）

传送门

题意简述：给出一个n∗mn*mn∗m的矩阵n,m≤1e8n,m\le1e8n,m≤1e8，支持矩形加，矩形求和，强制在线。

思路：第一眼二维动态开点线段树，上网去搜有没有这种做法发现会被卡时空

然后心态爆炸，居然不能直接树套树233.

然后想起了一个叫做二维前缀和+差分的东西（二维树状数组的时候用过），貌似维护二维差分数组的前缀和就完了，这东西不是可以离散化+主席数吗？

上网一搜发现是正解，然后点开了clarisclarisclaris的代码发现看不懂。

无奈之下自己yyyyyy了一波（丑

代码：

#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline ll read(){
    ll ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
const int N=8e5+5,M=5e6+5;
struct Node{
    ll v,x,y,z;
    friend inline Node operator+(const Node&a,const Node&b){return (Node){a.v+b.v,a.x+b.x,a.y+b.y,a.z+b.z};}
};
struct Upd{ll x,y,v;}upd[N<<1];
namespace SGT{
    #define lc (son[p][0])
    #define rc (son[p][1])
    #define mid (l+r>>1)
    Node val[M];
    int son[M][2],tot=0;
    inline void update(int&p,int o,int l,int r,int k,Node t){
        if(k>r)return;
        val[p=++tot]=val[o]+t,lc=son[o][0],rc=son[o][1];
        if(l==r)return;
        k<=mid?update(lc,son[o][0],l,mid,k,t):update(rc,son[o][1],mid+1,r,k,t);
    }
    inline Node query(int p,int l,int r,int ql,int qr){
        if(!p||ql>qr||ql>r||qr<l)return (Node){0ll,0ll,0ll,0ll};
        if(ql<=l&&r<=qr)return val[p];
        if(qr<=mid)return query(lc,l,mid,ql,qr);
        if(ql>mid)return query(rc,mid+1,r,ql,qr);
        return query(lc,l,mid,ql,mid)+query(rc,mid+1,r,mid+1,qr);
    }
    #undef mid
}
int n,m,k,q,rt[N],vx[N],vy[N],sx=0,sy=0,tot=0,sig=0;
inline bool cmp(const Upd&a,const Upd&b){return a.x<b.x;}
inline int find(int a[],int len,int x){
    int ans=0,l=1,r=len;
    while(l<=r){
        int mid=l+r>>1;
        if(a[mid]<=x)l=(ans=mid)+1;
        else r=mid-1;
    }
    return ans;
}
inline ll query(int x,int y){
    int px=find(vx,sx,x),py=find(vy,sy,y);
    Node tmp=SGT::query(rt[px],1,sy,1,py);
    return (ll)tmp.v*(x+1)*(y+1)-(ll)tmp.x*(x+1)-(ll)tmp.y*(y+1)+tmp.z;
}
int main(){
    n=read(),m=read(),k=read(),q=read();
    for(ri i=1,x1,y1,x2,y2,v;i<=k;++i){
        x1=read(),x2=read(),y1=read(),y2=read(),v=read();
        if(!v)continue;
        upd[++tot]=(Upd){x1,y1,v};
        upd[++tot]=(Upd){x2+1,y1,-v};
        upd[++tot]=(Upd){x1,y2+1,-v};
        upd[++tot]=(Upd){x2+1,y2+1,v};
        vx[++sx]=x1,vx[++sx]=x2+1;
        vy[++sy]=y1,vy[++sy]=y2+1;
    }
    sort(vx+1,vx+sx+1),sx=unique(vx+1,vx+sx+1)-vx-1;
    sort(vy+1,vy+sy+1),sy=unique(vy+1,vy+sy+1)-vy-1;
    sort(upd+1,upd+tot+1,cmp),rt[sig=0]=0;
    for(ri i=1,x,y,px,py;i<=tot;++i){
        ll v=upd[i].v;
        x=upd[i].x,y=upd[i].y;
        py=find(vy,sy,y);
        if(upd[i].x!=upd[i-1].x||i==1)++sig,rt[sig]=rt[sig-1];
        SGT::update(rt[sig],rt[sig],1,sy,py,(Node){v,(ll)y*v,(ll)x*v,(ll)x*y*v});
    }
    ll lastans=0;
    for(ri i=1,x1,x2,y1,y2;i<=q;++i){
        x1=lastans%n+1,x2=(lastans+read())%n+1;
        if(x1>x2)swap(x1,x2);
        y1=lastans%m+1,y2=(lastans+read())%m+1;
        if(y1>y2)swap(y1,y2);
        cout<<(lastans=query(x2,y2)-query(x1-1,y2)-query(x2,y1-1)+query(x1-1,y1-1))<<'\n';
    }
    return 0;
}

巴特西

2019.01.22 bzoj2874: 训练士兵（主席树）

最新文章

热门文章