脑子一抽想复杂了…

懵逼的 题目

扯淡的 题解

我们记一个采矿点采到的矿总数$A_i$, 第一次被这个采矿点采到的矿总数为$B_i$

然后我们考虑这个采矿点对答案的贡献, 为$(2_{B_i} - 1) \cdot 2^{A_i - B_i}$

因为每个之前已经选过的点如果要对答案再产生贡献的话都要和没选过一些点来配对…是不是很好理解?

比赛的时候写了个复杂度肥肠正确的$n\lg n$的线段树分治来找的$A_i, B_i$

结果被卡常了(比赛的时候还写挂了)…

沙茶的 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#define LL long long
#define pii pair<int, int>
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define INF (0x7fffffff)
#define MAXN (100000 + 5)
#define MAXZ (300000 + 5)
#define Aufun (998244353)
using namespace std;
struct node
{
    int le, ri, zz;
    set<int> hvntbeen;
} b[MAXZ << 3];
int n, m, a[MAXN], sora[MAXZ];
pii mine[MAXN];
LL ans;
queue<int> tosolve;
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    b[dq].zz = 0;
    if (le == ri)
        return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
}
void xg1(int dq, int le, int ri, int zh)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].hvntbeen.insert(zh);
        ++b[dq].zz;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        xg1(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg1(LS(dq), le, ri, zh);
    else
        xg1(LS(dq), le, mi, zh), xg1(RS(dq), mi + 1, ri, zh);
}
void xg2(int dq, int le, int ri, int zh)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        b[dq].hvntbeen.erase(zh);
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi)
        xg2(RS(dq), le, ri, zh);
    else if (ri <= mi)
        xg2(LS(dq), le, ri, zh);
    else
        xg2(LS(dq), le, mi, zh), xg2(RS(dq), mi + 1, ri, zh);
}
LL fp(int bx)
{
    if (!bx)
        return 1;
    LL re = fp(bx >> 1);
    re = (re * re) % Aufun;
    if (bx & 1)
        re = (re << 1) % Aufun;
    return re;
}
void cx(int dq, int wz, int zz, int fz)
{
    fz += b[dq].hvntbeen.size(), zz += b[dq].zz;
    for (set<int>::iterator i = b[dq].hvntbeen.begin(); i != b[dq].hvntbeen.end(); i++)
        tosolve.push(*i);
    if (b[dq].le == b[dq].ri)
    {    
        ans = (ans + (fp(fz) - 1) * fp(zz - fz)) % Aufun;
        while (ans < 0)
            ans += Aufun;
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (wz <= mi)
        cx(LS(dq), wz, zz, fz);
    else
        cx(RS(dq), wz, zz, fz);
}
int main()
{
//    freopen("in.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &mine[i].first, &mine[i].second), sora[++sora[0]] = mine[i].first, sora[++sora[0]] = mine[i].second;
    for (int i = 1; i <= m; i++)
        scanf("%d", &a[i]), sora[++sora[0]] = a[i];
    sort(sora + 1, sora + sora[0] + 1);
    sora[0] = unique(sora + 1, sora + sora[0] + 1) - sora - 1;
    js(1, 1, sora[0]);
    for (int i = 1; i <= n; i++)
    {
        mine[i].first = lower_bound(sora + 1, sora + sora[0] + 1, mine[i].first) - sora;
        mine[i].second = lower_bound(sora + 1, sora + sora[0] + 1, mine[i].second) - sora;
        xg1(1, mine[i].first, mine[i].second, i);
    }
    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; i++)
    {
        a[i] = lower_bound(sora + 1, sora + sora[0] + 1, a[i]) - sora;
        cx(1, a[i], 0, 0);
        while (!tosolve.empty())
        {
            int dq = tosolve.front();
            tosolve.pop();
            xg2(1, mine[dq].first, mine[dq].second, dq);
        }
    }
    printf("%lld", ans);
    return 0;
}

/*
3 2
7 11
1 5
3 8
4
7
*/

By 联赛钦定爆零的 Cansult