牛客网暑期ACM多校训练营（第二场）J 树状数组解法

J题做法:

我们通过差分(其实就是二维前缀和)可以在O(nm)的时间求出每个点被撒了几次肥料

然后我们可以对每种植物分开求被撒了几次相同种类的肥料，然后判断被撒肥料的次数是否等于被撒的相同种类肥料的次数来确定这个植物的死活

首先我们需要学会二维差分，这个怎么做呢？我们发现如果我们想对(x1,y1) (x2,y2)这个矩形内所有元素+1

我们可以通过a[x1][y1]++,a[x1][y2+1]--,a[x2+1][y1]--,a[x2+1][y2+1]++这四个操作来实现

我们对这四个点进行加减后，再对矩阵求一次二维前缀和，这时候的效果就是整个矩形+1了

大家可以通过这个代码了解二维差分的做法，通过修改x1 y1 x2 y2就能做到矩阵+1。

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[55][55];
int main()
{
    int x1=2,y1=2,x2=6,y2=8;
    a[x1][y1]++,a[x1][y2+1]--,a[x2+1][y1]--,a[x2+1][y2+1]++;
    for(int i=1;i<=10;i++)
        for(int j=1;j<=10;j++)
        a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];///二维前缀和
    for(int i=1;i<=10;i++,puts(""))
        for(int j=1;j<=10;j++)
            printf("%d ",a[i][j]);
    return 0;
}

然后我们开始考虑如何求每种的植物被撒了几次肥料。

我们要分别求n*m种植物被撒了几次肥料，所以我们肯定不能每一次都通过二维前缀和来维护被撒了几次肥料。

这时候我们发现这其实是个二维偏序的问题，我们对每种植物的贡献排序，然后用树状数组维护一下就好了。众所周知二维偏序的做法复杂度是一个log的，我们一共有n*m次操作，所以总复杂度为O(n*m*log(n*m))

具体怎么维护呢，我们通过对x和y坐标排序，按照顺序把贡献加到树状数组里，树状数组里前面的元素的x坐标一定是小于等于当前元素的，我们只需要求树状数组内<=y的和就能统计出x,y都<=y的元素和

注意一点，当x和y相等的时候，询问一定要在修改后面，排序时候判断一下就行了。

注意清空树状数组的时候为了保证复杂度，我们只能重新做一次之前的修改，把负的权值加上去。(更新，其实不需要清空树状数组，因为你每次加减的一定是个矩形，一个矩形有两个相等横坐标点且一个为1一个为-1，两个刚好能消掉)

具体代码如下


	#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<vector>
using namespace std;
int c[5100010];
int n,m;
int id(int i,int j){
    return i*(m+2)+j;
}
struct node{
    int x1,y1,x2,y2;
    void in(){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    }
};
struct nod{
    int x,y,val;
    bool operator < (const nod &b)const{
        if(x==b.x&&y==b.y){
            return abs(val)>abs(b.val);
        }
        if(x==b.x)
            return y<b.y;
        return x<b.x;
    }
};
vector<nod>vd[1100010];
int bit[1100010];
void add(int pos,int x){
    while(pos<=m+1){
        bit[pos]+=x;
        pos+=pos&-pos;
    }
}
int sum(int pos){
    int Sum=0;
    while(pos){
        Sum+=bit[pos];
        pos-=pos&-pos;
    }
    return Sum;
}
int main()
{
    int t,x;
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&x);
            vd[x].push_back(nod{i,j,0});
        }
    node now;
    while(t--){
        now.in();
        int k;
        scanf("%d",&k);
        vd[k].push_back(nod{now.x1,now.y1,1});
        vd[k].push_back(nod{now.x2+1,now.y2+1,1});
        vd[k].push_back(nod{now.x1,now.y2+1,-1});
        vd[k].push_back(nod{now.x2+1,now.y1,-1});
        c[id(now.x1,now.y1)]++;
        c[id(now.x2+1,now.y2+1)]++;
        c[id(now.x1,now.y2+1)]--;
        c[id(now.x2+1,now.y1)]--;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[id(i,j)]+=c[id(i-1,j)]+c[id(i,j-1)]-c[id(i-1,j-1)];
        }
    }
    int ans=0;
    for(int i=0;i<=n*m;i++){
        sort(vd[i].begin(),vd[i].end());
        for(int j=0;j<vd[i].size();j++){
            if(vd[i][j].val==0){
                if(c[id(vd[i][j].x,vd[i][j].y)]==sum(vd[i][j].y))
                    ans++;
            }
            else {
                add(vd[i][j].y,vd[i][j].val);
            }
        }
        for(int j=0;j<vd[i].size();j++)
            if(vd[i][j].val)
            add(vd[i][j].y,-vd[i][j].val);
    }
    printf("%d\n",n*m-ans);
    return 0;
}

比赛时候写的代码不太好看--不过大概意思差不多那个node结构体其实没有卵用，我就只用来读入了