AT_abc106_d题解

· · 题解

传送门

首先想到先预处理所有 l 和 r 的答案。

刚开始想到的是对于每一个 l，r，可以求出排除掉左端点在 1 到 l-1 的区间的区间数和排除掉右端点在 r+1 到 n 的区间的区间数，最后用这两个区间数的和减去总数 m 即可得到答案，因为这么算的话相当于左端点在 1 到 l-1 的区间数和右端点在 r+1 到 n 的区间数被算了一次，中间的也就是我要求的区间数被算了两次，减去总数就会把每个部分都消掉一次，最后我们要求的区间的区间数就只被算了一次。

但是这么想其实是错的，因为这样子做遗漏了一种区间，这种是包含了要求的区间 l 到 r 的。在计算的时候这种区间比较特殊，它既是属于左端点在 1 到 l-1 的区间，又是属于右端点在 r+1 到 n 的区间，所以它在做加法的过程中不会被算，却在做减法的过程中被计算，所以现在还需加上这样的一种区间的数量。

于是我就有了一种奇怪的处理方式：使用优先队列，关键字为右端点，从小到大，如果一个区间左端点小于 l 就入队，在后面枚举 r 的时候如果这个区间右端点小于等于 r 的就出队，统计目前还在队内的数量。但是这么做跑的很慢，还得优化。

其实很容易发现，使用优先队列的原因是因为不保证区间右端点有序，所以只需要先对于所有区间按照右端点从小到大排序，后面处理时就可以直接按照顺序取出区间右端点扔进 vector 里，在用一个变量表示目前属于这种特殊区间的在取出的右端点序列中下标最靠前的下标，因为这么做可以很方便地去除右端点已经小于等于 r 的区间的数量。

最后询问时直接输出对应的区间的答案即可。

CODE:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,q;
int l[200010],r[200010];
int ql[100010],qr[100010];
int vl[510],vr[510];
int ans[510][510];
vector<int> v;
struct aaa
{
    int lll,rr;
}a[200010];
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        vl[l[i]]++,vr[r[i]]++;
        a[i].lll=l[i],a[i].rr=r[i];
    }
    for(int i=1;i<=n;i++) vl[i]+=vl[i-1],vr[i]+=vr[i-1];
    sort(a+1,a+m+1,[](aaa x,aaa y){return x.rr<y.rr;});
    for(int i=1;i<=n;i++)
    {
        int sum=m-vl[i-1],tot=0,ss=0;
        for(int j=1;j<=m;j++)
            if(a[j].lll<i) v.push_back(a[j].rr),tot++;
        for(int j=i;j<=n;j++)
        {
            int s=m-(vr[n]-vr[j]);
            while(1)
            {
                if(ss>=tot) break;
                if(v[ss]>j) break;
                ss++;
            }
            ans[i][j]=s+sum-m+tot-ss;
        }
        v.clear();
    }
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",ans[l][r]);
    }
    return 0;
}