menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[二维偏序+三维偏序]HHHOJ183【Drinks】题解
apps HHHOJ
local_offer 查看标签
comment 0 条评论

解题报告

很明显至多选 $3$ 个就能构成一种方案,所以我们只需要考虑选 $1,2,3$ 个的情况就行了。

考虑不合法的情况,即物品之间有包含的情况,如:

1 1 1 | 3 2 2
2 2 2 | 2 1 1
      | 1 3 3

左边那个(一个完全包含另一个)是选 $2$ 个不合法的情况,右边那个(只要选两个,另一个被包含了)是选 $3$ 个不合法的情况。不难发现选 $2$ 个不合法的情况就是三维偏序问题,而选 $3$ 个不合法的情况只会出现在其中一个有两个位置包含另外两个的时候,是二维偏序问题。

求选 $3$ 个不合法的情况时,要对三个位置两两做二维偏序,会发现是有重复的:

1 1 1
2 2 2
3 3 3

重复的部分就是一个完全包含了另外两个,需要加回来两次。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,c[maxn+5],num[maxn+5],tp;struct data {int s[3],ID;} a[maxn+5],tem[maxn+5];LL ans;

inline void Clear(int x) {for (int i=x;i<=n;i+=i&-i) c[i]=0;}
inline void Update(int x,int tem) {for (int i=x;i<=n;i+=i&-i) c[i]+=tem;}
inline int Sum(int x) {int sum=0;for (int i=x;i;i-=i&-i) sum+=c[i];return sum;}
void msort(int L,int R){
    if (L==R) return;int mid=L+(R-L>>1);msort(L,mid);msort(mid+1,R);
    for (int j=mid+1,i=L;j<=R;num[a[j].ID]+=Sum(a[j].s[2]),j++)
        while (i<=mid&&a[i].s[1]<=a[j].s[1]) Update(a[i++].s[2],1);
    for (int i=L;i<=mid;i++) Clear(a[i].s[2]);for (int k=L;k<=R;k++) tem[k]=a[k];
    for (int k=L,i=L,j=mid+1;k<=R;k++) a[k]=tem[(j>R||i<=mid&&tem[i].s[1]<tem[j].s[1])?i++:j++];
}
inline bool cmp(const data &a,const data &b) {return a.s[tp]<b.s[tp];}
inline LL Count(int A,int B,LL ans=0){
    tp=A;sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++) c[i]=0;
    for (int i=1,s;i<=n;i++) s=Sum(a[i].s[B]),ans+=(LL)s*(s-1)>>1,Update(a[i].s[B],1);return ans;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);ans=n+((LL)n*(n-1)>>1)+((LL)n*(n-1)*(n-2)/6);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].s[0],&a[i].s[1],&a[i].s[2]),a[i].ID=i;
    tp=0;sort(a+1,a+1+n,cmp);msort(1,n);for (int i=1;i<=n;i++) ans-=num[i];
    ans-=Count(0,1)+Count(0,2)+Count(1,2);for (int i=1;i<=n;i++) ans+=(LL)num[i]*(num[i]-1);
    printf("%lld\n",ans);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up