ZigZagK的博客
[计数]Codeforces1028D【Order book】题解
2018年8月31日 09:41
查看标签

题目概述

有 $n$ 次操作,每次操作可以:1.加入一个A/B类型值为 $p$ 的元素(保证 $p$ 互不相同)。2.删去值为 $p$ 的元素,保证之前出现过。同时保证每次所有加入的A类型的元素均大于B类型的元素,且删去的时候会删除最小的A或最大的B。但是现在加入操作的类型丢失了,问有多少种可以满足的方案。

解题报告

可能不难,我太菜了……题目里的保证非常强力,可以发现这样的性质:删除 $p$ 之后,新的最小A一定是比 $p$ 大的第一个元素,新的最大B一定是比p小的第一个元素。那么我们可以维护 $L,R$ 表示上次删除后的最大B和最小A(这样就确定了哪些是A哪些是B),然后删除时大力分类讨论一波:

  1. $p<L\lor R<p$ ,一定无解。
  2. $p=L\lor R=p$ ,删除是固定的,答案保持不变。
  3. $L<p\land p<R$ ,说明要删除的在新加的一些元素里面,由于这些元素还没有确定类型,所以答案$\times2$ 。

计算完贡献之后求出新的 $L,R$ ,来确定下次的贡献。

等下……如果最后没有出现删除,最后的那些加入怎么计算?如果 $p<L\lor R<p$ 的话这些对答案没有影响,而如果在 $L<p\land p<R$ 有 $m$ 个加入,那么答案会$\times(m+1)$ ,因为分界点可以是里面的任何一个。

示例程序

#include<cstdio>
#include<set>
using namespace std;
typedef long long LL;
const int maxn=363304,MOD=1e9+7;

int n,L=-2e9,R=2e9,lst=1,ans=1;set<int> S;set<int>::iterator it;

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&n),S.insert(L),S.insert(R);n;n--){
        char s[10];int p;scanf("%s%d",s,&p);
        if (s[1]=='D') S.insert(p),lst+=L<p&&p<R; else{
            if (p<L||R<p) return puts("0"),0;if (L<p&&p<R) ans=((LL)ans<<1)%MOD;
            S.erase(p);it=S.upper_bound(p);R=*it;L=*(--it);lst=1;
        }
    }return ans=(LL)ans*lst%MOD,printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!