[IOI2015]teams 分组题解

前言

题解写到一半时突然 wmh 跑过来把我题解删了。 阿巴阿巴阿巴......

题解

思路

（pass：用 [i] 表示引理 i，找不到的用 ctrl+f。）

我们把题目中的 A_i 记为 L_i，B_i 记为 R_i，并把 k_i 从小到大排序。

首先考虑一个基础的贪心：对于一次询问中的 k_i，我们在所有剩余的满足条件的数（L_i \le k_i \le R_i）中贪心按 R_i 从小到大取，证明如下：

对于两个数 i 和 j（L_i,L_j\le k_i，R_i\le R_j）来说，对于 \forall l \in (i,n] 来说，都有 L_i,L_j \le k_i \le k_l，即这两个数在考虑 k_l 的贡献时只需要考虑 R 的限制。那么显然是把 R 大的留在后面更优。

但暴力模拟贪心会炸（O(n\times q)）。因为 q 的原因，因此下面的算法中不能用 i 去更新 k_j，而要以 k_j 去找满足条件的剩余的 i。

观察贪心过程，我们会发现他有一个优美的性质：只有一次操作时，对于所有满足的 L_i\le k_1 的数按 R_i 排序时，没被取过的数（也满足 L_i\le k_1）的集合一定满足他是一个从（排序的集合的）右端点开始的区间。这个容易在贪心的过程中证明。

由于这个优美的性质，若有第二次操作时，我们只需要考虑两个部分

• 1. 左端点满足 k_1<L_i\le k_2 的数，他们都没有被取过。我们可以贪心取。
• 2. （[1]）左端点满足 L_i\le k_1 的部分，设 h 为没被取过的数中最小的右端点。若满足 h\le k_2，说明我们可以按第一个部分的方案取，而不会取到合法的方案，因为 \forall R_i\ge h,L_i\le k_1 都没被取过，且 h\le k_2，即 \forall R_i\ge k_2,L_i\le k_1 也没有被取过 ；若 h>k_2，则我们可以统计所有没被取过的数，他们都能对 k_2 造成贡献。

知道了能取的数的集合，那么我们就要讨论剩下的数（考虑 h_1> k_i 的情况，显然个数固定）。直接的话这样算的：

（红线标的部分为 h_1=R_i）

那么就是先从下到上取到第二个集合直到红线部分，再按 R_i 依次从小到大取。BUT，我们发现了一个事情——当我们没有取到红线部分时，对于 L_i\le k_2 的数按 R_i 从小到大排序时，剩下的数的集合不一定在上面连续。但是取过红线以后又满足了上面说的性质。

转化一下判断方法，即当我们剩余的数的名额从前往后贪心的取，（就相当于贪心地从后往前取对 k_2 能造成贡献的数）。设此时 h_2 为此时满足 k_1< L_i\le k_2 的剩余的数中 R_i 的最小值。那么若 h_2\ge h_1 ，则能取到红线部分，否则取不到。

基此，我们发现了一个妙妙的方法：（[2]）若按上面的判断方法能越过红线的话，L_i\le k_1 和 k_1\le L_i \le k_2 的剩余部分与 L_i \le k_2 的部分贪心按 R_i 从大到小取所得的剩余部分等同。否则不相等。（[3]）当不相等的时候，总体贪心取的方案恰好等同于对 k_1<L_i\le k_2 中贪心取剩余的数的方案——总结，都可以贪心取。

因此，若我们按照上面的方法合并的话，我们发现每个区间剩余的数的右端点的最小高度单调递减。

实现

我们睿智地看了一眼，发现这和单调栈非常像。因此我们用单调栈进行操作：

（若单调栈中没有数，默认为 0。）

• 记 hater_i（夹带私货.jpg） 表示元素 i 与单调栈上一个元素（记为 j）中满足 k_j<L_i\le k_i 中剩余的数的 R_i 的最小值。记 s_i 表示满足 k_1......k_i 后的剩余的数的数量。单调栈从大到小维护 i

• 对于一个新的元素 i 来说，我们找到单调栈中满足 hater_i 大于 i的第一个数（[1]）记为 j（由于栈中元素的最小高度大于等于 j 的，所以都可以这样计算），然后用数据结构求解在满足 k_j\le L_l\le k_i,R_l\ge k_i 的数量。判断是否有 k 个数（s_i+ 个数 \ge k_i，记为 sum）。

• 然后对于栈中的每个元素（设为 j），我们记录 h 表示在从前往后贪心的取中，在满足 k_j<L_l\le k_i 数中剩余的数的 R_l 的最小值。若 h>hater[i]，则弹出栈中的元素（[2]）。

容易发现，上面所说的数据结构就是主席树，可以满足：

• 求 k_j<L_l\le k_i，R_l\ge k_i 的数量。

• 求出 k_j<L_l\le k_i 中，R_i 从大到小排序的第 k 位。

注意，由于可能没有数可取，这时定义 hater_i=n+1。

由于数据范围很小，所以不用离散化。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
#define pb push_back
using namespace std;
const int N=1e7+1e3;
struct Segment_Tree
{
    int tot;
    int rt[N],ls[N],rs[N];
    int val[N];
    #define midd ((l+r)>>1)
    int New(){return ++tot;}
    void insert(int &x,int y,int l,int r,int p)
    {
        x=New();val[x]=val[y]+1; 
        ls[x]=ls[y];rs[x]=rs[y];
        if(l==r)return;
        int mid=midd;
        if(p<=mid)insert(ls[x],ls[y],l,mid,p);
        else insert(rs[x],rs[y],mid+1,r,p);
    }
    int qpos(int x,int y,int l,int r,int k)
    // 求出从大到小的第 i 位的 值
    {
        if(l==r)return l;
        int t=val[rs[x]]-val[rs[y]],mid=midd;
        if(t>=k)return qpos(rs[x],rs[y],mid+1,r,k);
        return qpos(ls[x],ls[y],l,mid,k-t);
    }
    int query(int x,int y,int l,int r,int p)
    //求出大于等于 p 的数量
    {
        if(!x)return 0;
        if(l==r)return val[x]-val[y];
        int mid=midd;
        if(p<=mid)return query(ls[x],ls[y],l,mid,p)+val[rs[x]]-val[rs[y]];
        return query(rs[x],rs[y],mid+1,r,p);
    }
    #undef midd
}T;
int n,m;
int k[N];
pii a[N];
stack<int>st;
int hater[N],s[N];
void work()
{
    stack<int>st;while(!st.empty())st.pop();
    for(int i=1;i<=m;i++)
    {
        while(!st.empty()&&hater[st.top()]<k[i])st.pop();
        int pre=(st.empty()?0:st.top());
        int sum=s[pre]+T.query(T.rt[k[i]],T.rt[k[pre]],1,n+1,k[i])-k[i];
        if(sum<0)return puts("0"),void();
        int h=T.qpos(T.rt[k[i]],T.rt[k[pre]],1,n+1,sum-s[pre]);
        while(!st.empty()&&h>=hater[st.top()])
        {
            st.pop();pre=(st.empty()?0:st.top());
            h=T.qpos(T.rt[k[i]],T.rt[k[pre]],1,n+1,sum-s[pre]);
        }
        st.push(i);hater[i]=h;s[i]=sum;
    }
    puts("1");
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&a[i].fi,&a[i].se);
    sort(a+1,a+n+1);
    for(int i=1,j=1;i<=n+1;i++)
    //注意 n+1
    {
        T.rt[i]=T.rt[i-1];
        while(j<=n&&a[j].fi==i)T.insert(T.rt[i],T.rt[i],1,n+1,a[j].se),j++;
    }
    int _;scanf("%d",&_);
    while(_--)
    {
        scanf("%d",&m);
        for(int i=1;i<=m;i++)scanf("%d",&k[i]);
        sort(k+1,k+m+1);
        work();
    }
    return 0;
}

后记

这题希望评个黑（这样我就有黑题题解了）。

感谢人 win legendgod 大佬 的指导 。