BZOJ1176 Mokia cdq分治

BZOJ1176 Mokia

需要维护两种操作:1.单点+值,2.区间查询

考虑离线(在线据说也可以但是我不会(kdtree?)

首先考虑矩阵查询,等价于四个小矩阵查询然后二维前缀和

现在我们的操作变成————

计算某一个点的二维前缀贡献和

由于初始值一样,可以开始把初始值算出来,然后每次只需要考虑单点修改这个矩阵的贡献。

把所有询问按照x顺序排序

然后把这么多的询问分治

每次分治只考虑左边的修改对右边的查询的贡献

然后按照类似归并的思路,如果这个点的id小于m放在左边,否则放在右边

于是又被转化成了完全相同的两个子问题。

其中修改考虑树状数组(快速求出前缀和)

然后时间复杂度差不多$nlognlogw$每一次树状数组修改$logw$,然后分治算问题是$nlogn$

就这个沙雕代码调了我2h

2h

((菜死会儿~

/*Never Say Die!*/
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
using namespace std;
#define MAXN 210006
struct query{ int x,y,opt,c,idx,id; }q[MAXN],tmp[MAXN];int cnt,ct;
bool cmp(query a,query b){ return a.x != b.x? a.x<b.x : a.y != b.y ? a.y < b.y : abs(a.opt) < abs(b.opt); }
int n,m,S[2000006];
inline void add(int x,int c){
    for(;x <= m;x += x&-x) S[x] += c;
}
inline int sum(int x){
    int res = 0;
    for(;x > 0;x -= x&-x) res += S[x];
    return res;
}
int ans[MAXN];
void solve(int l,int r){
    if(l == r) return;
    int m = l + r >> 1;
    for(register int i=l;i<=r;++i)
        if(q[i].id <= m&&!q[i].opt) add(q[i].y,q[i].c);
        else if(q[i].id > m && q[i].opt)ans[q[i].idx] += sum(q[i].y)*q[i].opt;
    for(register int i=l;i<=r;++i) if(q[i].id <= m&&!q[i].opt) add(q[i].y,-q[i].c);
    int ll = l , lll = m+1;
    for(register int i=l;i<=r;++i) if(q[i].id <= m) tmp[ll++] = q[i]; else tmp[lll++] = q[i];
    for(int i=l;i<=r;++i) q[i] = tmp[i];
    solve(l,m),solve(m+1,r);
}
int main(){
    cin >> n >> m;++m;
    int opt,x1,x2,y1,y2;
    while(scanf("%d",&opt)) {
        if(opt == 1) ++cnt,scanf("%d%d%d",&q[cnt].x,&q[cnt].y,&q[cnt].c),++q[cnt].x,++q[cnt].y,q[cnt].opt = 0,q[cnt].id = cnt;
        else if(opt == 2)
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2),
                    ++ct,
                    ++cnt,q[cnt] = (query){x1,y1,1,0,ct,cnt},
                    ++cnt,q[cnt] = (query){x2+1,y2+1,1,0,ct,cnt},
                    ++cnt,q[cnt] = (query){x1,y2+1,-1,0,ct,cnt},
                    ++cnt,q[cnt] = (query){x2+1,y1,-1,0,ct,cnt},
                    ans[ct] = (y2 - y1+1) * (x2 - x1+1) * n;
        else break;
    }
    sort(q+1,q+1+cnt,cmp);
    solve(1,cnt);
    for(int i=1;i<=ct;++i) printf("%d\n",ans[i]);
}