【BZOJ1176】Mokia

1176: [Balkan2007]Mokia

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 2184 Solved: 983
[Submit][Status][Discuss]

Description

维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

Input

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左下角为(x1,y1),右上角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

Output

对于每个输入2,输出一行,即输入2的答案

Sample Input

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

保证答案不会超过int范围

Source

不是很懂初始值是S

我加上就WA 不加就A

顺便贴代码这样和之前一模一样了

cdq分治

/*To The End Of The Galaxy*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#define debug(x) cerr<<#x<<"="<<x<<endl
#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
struct task
{
    int id,x,y,v,t;
}query[800005],tmpq[800005];
int s[2000005];
int bel[800005];
int tot=0;
int n,m;
int ans[800005];
int c[800005];
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
void modify(int x,int v)
{
    for(int i=x;i<=n;i+=lowbit(i))
    {
        s[i]+=v;
    }
}
int sum(int x)
{
    int tot=0;
    for(int i=x;i>=1;i-=lowbit(i))
    {
        tot+=s[i];
    }
    return tot;
}
bool operator < (task a,task b)
{
    return a.x<b.x;
}
void solve(int l,int r)
{
    if(l==r)return;
    solve(l,mid);solve(mid+1,r);
    int i=l,j=mid+1,last=0;
    while(j<=r)
    {
        while(i<=mid&&query[i].t==2)
        {
            i++;
        }
        while(j<=r&&query[j].t==1)
        {
            j++;
        }
        if(i<=mid&&query[i].x<=query[j].x)
        {
            modify(query[i].y,query[i].v);
            last=i;i++;
        }
        else if(j<=r)
        {
            ans[query[j].id]+=sum(query[j].y);
            j++;
        }
    }
    for(int i=l;i<=last;i++)
    {
        if(query[i].t==1)
        modify(query[i].y,-query[i].v);
    }
    merge(query+l,query+1+mid,query+1+mid,query+r+1,tmpq+l);
    for(int i=l;i<=r;i++)
    {
        query[i]=tmpq[i];
    }
}
int main()
{
    int S,t,x1,x2,y1,y2;
    S=init();n=init();
    while(t=init(),t!=3)
    {
        if(t==1)
        {
            ++m;
            query[m].id=m;query[m].t=t;query[m].x=init();query[m].y=init();query[m].v=init();
        }
        else
        {
            x1=init();y1=init();x2=init();y2=init();
            c[++tot]=m;
            //ans[m+1]+=(y2-y1+1)*(x2-x1+1)*S;
            ++m;
            query[m].id=m;query[m].t=t;query[m].x=x1-1;query[m].y=y1-1;
            ++m;
            query[m].id=m;query[m].t=t;query[m].x=x1-1;query[m].y=y2;
            ++m;
            query[m].id=m;query[m].t=t;query[m].x=x2;query[m].y=y1-1;
            ++m;
            query[m].id=m;query[m].t=t;query[m].x=x2;query[m].y=y2;            
        }
    }
    solve(1,m);
    for(int i=1;i<=tot;i++)
    {
        printf("%d
",ans[c[i]+1]-ans[c[i]+2]-ans[c[i]+3]+ans[c[i]+4]);
    }
    return 0;
}
/*
srO xudyh davidlee1999WTK linkct1999 Orz
compiler TDM-GCC 5.9.2
*/

View Code