牛客网多校第5场 I vcd 【树状数组+离散化处理】【非原创】

题目：戳这里

学习博客：戳这里

作者：阿狸是狐狸啦

n个点，一个点集S是好的，当且仅当对于他的每个子集T，存在一个右边无限延长的矩形，使的这个矩形包含了T，但是和S-T没有交集。

求有多少个这种集合。

画图找规律可得

当我们求的集合中的点只有一个时，肯定满足要求。

当有两个点且这两个点y坐标不相等也满足要求。

当有三个点组成一个小于号形状的集合S时，这个集合S的子集T一定与S-T无交集，当组成一个大于号时。我们取大于号左边的两个端点组成的T集合一定与右边的那个端点有交集。

当有四个点组成的S点集他一定存在一个子集T和S-T有交集。

所以我们计算小于等于三个点的情况就行了。

一的情况直接是n。

二的情况总的情况减去y坐标相等的点的情况就行了。

三的情况就是数一下有多少个小于号的情况，树状数组维护一下就行了。

附ac代码：

  1 #include <cstdio>

  2 #include <cstring>

  3 #include <algorithm>

  4 #include <queue>

  5 #include <stack>

  6 #include <iostream>

  7 using namespace std;

  8 typedef long long ll;

  9 const int maxn = 2 * 1e5 + 10;

 10 const ll mod =  998244353;

 11 struct nod

 12 {

 13     ll x;

 14     ll y;

 15 }coo[maxn];

 16 ll cnt[maxn];

 17 ll c[maxn<<2];

 18 ll y[maxn];

 19 ll n;

 20 bool cmp(nod a, nod b)

 21 {

 22     return a.x > b.x;

 23 }

 24 ll pmul(ll a, ll b)

 25 {

 26     ll res = 0;

 27     while(b)

 28     {

 29         if(b&1)

 30             res = (res + a) % mod;

 31         b >>= 1;

 32         a = (a + a) % mod;

 33     }

 34     return res;

 35 }

 36 ll pmod(ll a, ll b)

 37 {

 38     ll res = 1;

 39     while(b)

 40     {

 41         if(b&1)

 42             res = pmul(res, a) % mod;

 43         b >>= 1;

 44         a = pmul(a, a) % mod;

 45     }

 46     return res;

 47 }

 48 ll gets(int x)

 49 {

 50     ll ans = 0;

 51     while(x)

 52     {

 53         ans = (ans + c[x]) % mod;

 54         x -= x & (-x);

 55     }

 56     return ans;

 57 }

 58 void updat(int x, ll ad)

 59 {

 60     while(x <= n)

 61     {

 62         c[x] = (c[x] + ad) % mod;

 63         x += x & (-x);

 64     }

 65 }

 66 int main() {

 67

 68     scanf("%d", &n);

 69     for(ll i = 1; i <= n; ++i)

 70     {

 71         scanf("%d %d", &coo[i].x, &coo[i].y);

 72         y[i] = coo[i].y;

 73     }

 74     sort(y + 1, y + 1 + n);

 75     for(ll i = 1; i <= n; ++i)//这一步很有意思，把1e9的范围离散化到了1e5

 76     {

 77         ll u = lower_bound(y + 1, y + 1 + n, coo[i].y) - y;

 78         coo[i].y = u;

 79         ++cnt[u];

 80        // printf("%d u\n", u);

 81     }

 82     sort(coo + 1, coo + 1 + n, cmp);

 83     ll ans = n + n * (n - 1) / 2;

 84     ans %= mod;

 85     for(ll i = 1; i <= n; ++i)

 86     {

 87         ll u = cnt[i];

 88         if(u)

 89         ans = (ans - u * (u - 1) / 2) % mod;

 90     }

 91     ll up = 0, dw = 0;

 92     ll now = 1;

 93     for(ll i = 1; i <= n; ++i)

 94     {

 95         up = (gets(n) - gets(coo[i].y)) % mod;

 96         dw = gets(coo[i].y - 1) % mod;

 97         ans = (ans + up * dw % mod) % mod;

 98         for(;coo[i].x != coo[i + 1].x && now <= i; ++now)

 99         {

100             updat(coo[now].y, 1ll);

101         }

102     }

103     printf("%lld\n", ans % mod);

104     return 0;

105 }

巴特西

牛客网多校第5场 I vcd 【树状数组+离散化处理】【非原创】

最新文章

热门文章