Nowcoder farm ( 树状数组、二维前缀和、二维偏序 )

时间：2022-08-09 08:25:15

题目链接

分析 :

最简单的想法当然就是去模拟

直接对每个施肥料的操作进行模拟、然后计算贡献

但是这显然会超时、这题需要换一个思维

对于一个土地（也就是二维平面上的一个点）的种类是 T'

如果它被操作了 K1 次、那么如果我能知道所有用 T' 施肥的操作

对这块土地施肥的次数 K2、那么当 K1 == K2 的时候、这片土地就不会 Die

而当 K1 != K2 的时候、则这块土地就会 Die 、换句话说就是答案要加一

计算每个土地被操作的总次数

要知道每个土地被操作了多少次、可以利用二维前缀和的方式来计算贡献

假设操作矩形的左上角和右下角分别为 (x1, y1) 、(x2, y2)

那么可以用二维数组模拟这个矩形的四个顶点分别做加减操作

具体的就是 arr[x1][y1]++、arr[x1][y2+1]--、arr[x2+1][y1]--、arr[x2][y2]++

然后 N*M 地去遍历整个土地、利用这条式子 arr[i][j] += arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1]

最后 arr 这个二维数组中所有的数字表示的即为某一块土地被操作的总次数

计算被用于操作的肥料对其施肥的土地操作的总次数

如果仔细思考一下便会发现这个是一个很经典的二维偏序问题

如果你解决过类似 CDQ 分治的题目、那么这个便会很容易理解

对于每个种类的肥料、其可能被用于若干次施肥操作

施肥操作是一个矩形、可以将矩形操作分解成四个点的加减操作

也就是将一个操作变成四个操作、如果你熟悉 CDQ 分治、那么这个会好理解

可以发现对于每一个点、在二维平面上只有其左上角的操作点对它有影响

所以每次处理都将所有操作对于 X 轴先进行排序、然后利用树状数组维护 Y 轴

还有一开始的原矩形元素也应该被视作操作、保存到分治数组里面去、用于问询

可能很乱，看代码就清楚了

（最好是你先去熟悉偏序问题和CDQ分治、因为代码的很多细节都是套路操作、不赘述了）

#include<bits/stdc++.h>
#define LL long long
#define ULL unsigned long long

#define scl(i) scanf("%lld", &i)
#define scll(i, j) scanf("%lld %lld", &i, &j)
#define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k)
#define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l)

#define scs(i) scanf("%s", i)
#define sci(i) scanf("%d", &i)
#define scd(i) scanf("%lf", &i)
#define scIl(i) scanf("%I64d", &i)
#define scii(i, j) scanf("%d %d", &i, &j)
#define scdd(i, j) scanf("%lf %lf", &i, &j)
#define scIll(i, j) scanf("%I64d %I64d", &i, &j)
#define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k)
#define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k)
#define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k)
#define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l)
#define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l)
#define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l)

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(i) (i & (-i))
#define mem(i, j) memset(i, j, sizeof(i))

#define fir first
#define sec second
#define VI vector<int>
#define ins(i) insert(i)
#define pb(i) push_back(i)
#define pii pair<int, int>
#define VL vector<long long>
#define mk(i, j) make_pair(i, j)
#define all(i) i.begin(), i.end()
#define pll pair<long long, long long>

#define _TIME 0
#define _INPUT 0
#define _OUTPUT 0
clock_t START, END;
void __stTIME();
void __enTIME();
void __IOPUT();
using namespace std;
;

struct ARR{
    int r, c, op;
    ARR(){};
    ARR(int _r, int _c, int _o):r(_r), c(_c), op(_o){};
    bool operator < (const ARR & rhs) const{
        if(r == rhs.r && c == rhs.c) return abs(op) > abs(rhs.op);
        if(r == rhs.r) return c < rhs.c;
        return r < rhs.r;
    }
}; vector<ARR> arr[maxn];

int n, m, T;
];
int Bit[maxn];

inline void BitAdd(int i, int val)
{
    while(i <= m){
        Bit[i] += val;
        i += (i & (-i));
    }
}

int BitSum(int i)
{
    ) ;
    ;
    ){
        ret += Bit[i];
        i -= (i & (-i));
    }return ret;
}

void BitClean(int i)
{
    while(i <= m){
        Bit[i] = ;
        i += (i & (-i));
    }
}

int idx(int r, int c)
{ return r * m + c; }

int main(void){__stTIME();__IOPUT();

    sciii(n, m, T);

    ; i<=n; i++)
        ; j<=m; j++){
            int tmp; sci(tmp);
            arr[tmp].pb(ARR(i, j, ));
        }

    ; i<T; i++){
        int x1, y1, x2, y2, k;
        sciiii(x1, y1, x2, y2); sci(k);
        arr[k].pb(ARR(x1, y1, ));
        arr[k].pb(ARR(x1, y2+, -));
        arr[k].pb(ARR(x2+, y1, -));
        arr[k].pb(ARR(x2+, y2+, ));
        Cnt[idx(x1, y1)]++;
        Cnt[idx(x1, y2+)]--;
        Cnt[idx(x2+, y1)]--;
        Cnt[idx(x2+, y2+)]++;
    }

    ; i<=n; i++)
        ; j<=m; j++)
            Cnt[idx(i, j)] += Cnt[idx(i-, j)] +
                              Cnt[idx(i, j-)] -
                              Cnt[idx(i-, j-)];

//    for(int i=1; i<=n; i++,puts(""))
//        for(int j=1; j<=m; j++)
//            printf("%d ", Cnt[idx(i, j)]);

    ;
    ; i<=n*m; i++){
        sort(all(arr[i]));
        //printf("----- %d ------\n", i);
        ; j<(int)arr[i].size(); j++){
            //printf("$$=> %d %d %d\n", arr[i][j].r, arr[i][j].c, arr[i][j].op);
            ){
                if(Cnt[idx(arr[i][j].r, arr[i][j].c)] != BitSum(arr[i][j].c))
                    ans++;
            }else BitAdd(arr[i][j].c, arr[i][j].op);
        }
        ; j<(int)arr[i].size(); j++){
            )
                BitClean(arr[i][j].c);
        }
    }

    printf("%d\n", ans);

__enTIME();;}

void __stTIME()
{
    #if _TIME
        START = clock();
    #endif
}

void __enTIME()
{
    #if _TIME
        END = clock();
        cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl;
    #endif
}

void __IOPUT()
{
    #if _INPUT
        freopen("in.txt", "r", stdin);
    #endif
    #if _OUTPUT
        freopen("out.txt", "w", stdout);
    #endif
}

相关文章