【BZOJ5366】【Lydsy1805月赛】代码派对

容斥+二维前缀和即可。

首先一个naive的想法是枚举一个点(x,y)(x,y),用二维前缀和预处理出有多少个矩形包含(x,y)(x,y),设有kk个,那么给答案加上(k3)\binom{k}{3}。但是这样显然会算重。

注意到33个矩形的交要么是空,要么还是矩形,我们考虑只在交的左上角计数这33个矩形一次。也就是说,对于每个点(x,y)(x,y),我们要算有多少矩形三元组的交包含这个点,但是不包含(x1,y)(x-1,y)(x,y1)(x,y-1)

考虑容斥,可以发现这就等于包含(x,y)(x,y)的矩形三元组的数量,减去同时包含(x,y)(x,y)(x1,y)(x-1,y)的矩形三元组的数量,减去同时包含(x,y)(x,y)(x,y1)(x,y-1)的矩形三元组的数量,再加上同时包含(x,y)(x,y)(x1,y)(x-1,y)(x,y1)(x,y-1)的矩形三元组的数量。后面三个量的计算和第一个是类似的,只是要把矩形缩小一行和/或一列,直接二维前缀和即可。

时间复杂度O(T(n+10002))O(T(n+1000^2))

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("5366.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
ll c3(ll n){
    return n*(n-1)*(n-2);
}
struct qwq{
    int t[1002][1002];
    void init(){
        memset(t,0,sizeof(t));
    }
    void add(int x1,int y1,int x2,int y2,int v){
        if (x1>x2 || y1>y2)
            return;
        t[x1][y1]+=v;
        t[x1][y2+1]-=v;
        t[x2+1][y1]-=v;
        t[x2+1][y2+1]+=v;
    }
    void get(){
        for(int i=1;i<=1000;i++)
            for(int j=1;j<=1000;j++)
                t[i][j]+=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
    }
    int * operator [](int x){
        return t[x];
    }
}a,b,c,d;
int main(){
    init();
    int T=readint();
    while(T--){
        int n=readint();
        a.init(),b.init(),c.init(),d.init();
        while(n--){
            int x1=readint(),y1=readint(),x2=readint(),y2=readint();
            a.add(x1,y1,x2,y2,1);
            b.add(x1+1,y1,x2,y2,1);
            c.add(x1,y1+1,x2,y2,1);
            d.add(x1+1,y1+1,x2,y2,1);
        }
        a.get(),b.get(),c.get(),d.get();
        ll ans=0;
        for(int i=1;i<=1000;i++)
            for(int j=1;j<=1000;j++)
                ans+=c3(a[i][j])-c3(b[i][j])-c3(c[i][j])+c3(d[i][j]);
        printf("%lld\n",ans/6);
    }
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2018/05/29/bzoj5366/

隐藏