题目概述

CF853C

解题报告

直接求很麻烦，我们求不满足的个数。对于询问的矩形 $A$ ，我们划分出八个区域：

 | 0 | 1 | 2 |
 -------------
 | 3 | A | 4 |
 -------------
 | 5 | 6 | 7 |

这八个区域中不跨越 $A$ 的两个区域中的点组合就是不满足的。

所以对于每个询问我们要求出八个区域中点的个数，由于询问离线，我们用扫描线就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000,maxq=200000,maxt=maxq*16;

int n,Q,m,a[maxn+5],f[maxq+5][8],c[maxn+5];
struct data {int x,L,R,f;int *F;} q[maxt+5];

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
void Add(int A,int B,int C,int D,int *F){
    if (A<1 || B>n || C<1 || D>n || A>C || B>D) return;
    if (A>1) q[++m]=(data){A-1,B,D,-1,F};
    q[++m]=(data){C,B,D,1,F};
}
inline bool cmp(const data &a,const data &b) {return a.x<b.x;}
void Insert(int x,int y) {for (int i=x;i<=n;i+=i&-i) c[i]+=y;}
int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
#define C2(n) ((LL)(n)*((n)-1)>>1)
#define Count(a,b,c) ((LL)(a)*(b)+(LL)(a)*(c)+(LL)(b)*(c))
int main(){
    freopen("853C.in","r",stdin);freopen("853C.out","w",stdout);
    readi(n);readi(Q);for (int i=1;i<=n;i++) readi(a[i]);
    for (int i=1;i<=Q;i++){
        int A,B,C,D;readi(A);readi(B);readi(C);readi(D);
        Add(1,1,A-1,B-1,&f[i][0]);Add(1,B,A-1,D,&f[i][1]);
        Add(1,D+1,A-1,n,&f[i][2]);Add(A,1,C,B-1,&f[i][3]);
        Add(A,D+1,C,n,&f[i][4]);Add(C+1,1,n,B-1,&f[i][5]);
        Add(C+1,B,n,D,&f[i][6]);Add(C+1,D+1,n,n,&f[i][7]);
    }
    sort(q+1,q+1+m,cmp);
    for (int i=1,j=1;i<=n;i++)
        for (Insert(a[i],1);j<=m && q[j].x==i;j++)
            *q[j].F+=q[j].f*(Sum(q[j].R)-Sum(q[j].L-1));
    for (int i=1;i<=Q;i++){
        LL ans=C2(n);
        for (int j=0;j<8;j++) ans-=C2(f[i][j]);
        ans-=Count(f[i][0],f[i][1],f[i][2]);
        ans-=Count(f[i][5],f[i][6],f[i][7]);
        ans-=Count(f[i][0],f[i][3],f[i][5]);
        ans-=Count(f[i][2],f[i][4],f[i][7]);
        printf("%lld\n",ans);
    }
    return 0;
}