L - Intersection and Union Gym - 103993L

题目链接
题意：

op可以是交，并，异或，问$3^{n-1}$种情况的长度之和是多少。
我们正向做的话集合太多，没办法枚举所有的

因为数的大小是$3e5$所以我们可以枚举每个数，然后求他在整个集合中的贡献。

然后我们开始研究这三种操作，我们可以很明显发现以下规律：
假设第$i$个集合$S_i$，假设他里面含有某个数$x$
那么，上一步操作完成后：
假设集合中仍然含有$x$，那么∩和∪仍然含有$x$
假设集合中没有含有$x$，那么∪和$\oplus$含有$x$
所以我们发现无论怎样都含有两种情况，所以这一步的值可以计算为$2\ast 3^k$（k是前面符号的数量）

那么，我们这样操作受到的影响是很大的，因为我们枚举到$S_i$后，后面可能某一集合仍然会枚举到$x$，这样我们无法计算后面的情况；所以，我们必须固定一个值，这样我们可以让后面无法找到$x$；所以，我们可以每次都枚举包含$x$的最后一个集合。
这样的话我们就可以计算了，因为后面不再出现$x$，所以后面的情况是$2^k$（k是指后面符号的数量，指后面必须都选择$\cup$和$\oplus$），这样结合上面分析的，就可以计算出所有的情况了。

找到包含$x$的最后一个集合可以用线段树进行维护。

下面是AC代码：

#include
#include
#include
#include
using namespace std;
#define int long long
const int N=3e5+10;
const int mod=998244353;
//区间修改单点查询
struct SegmentTree
{
    int l,r;
    int res;//维护最大值
    int lazy;//区间修改懒标记
}tr[N*4];
void build(int u,int l,int r)
{
    tr[u]={l,r,0,0};
    if(tr[u].l==tr[u].r) return;
    int mid=tr[u].l+tr[u].r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}
void modify(int u,int l,int r,int val)
{
    if(tr[u].l>=l&&tr[u].r<=r) 
    {
        tr[u].res=val;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) modify(u<<1,l,r,val);
    if(r>mid) modify(u<<1|1,l,r,val);
}
void query(int u,int l,int &val)//val这里传地址，函数就不用返回最大值了
{
    val=max(val,tr[u].res);//如果没有包含这个l值，结果都是0，只有包含的才不是，思路很巧妙
    if(tr[u].r==tr[u].l) return;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid) query(u<<1,l,val);
    if(l>mid) query(u<<1|1,l,val);
}
int qmi(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
signed main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    build(1,0,300000);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        modify(1,l,r,i);
    }
    int res=0;
    for(int i=0;i<=300000;i++)
    {
        int val=0,sum=0;
        query(1,i,val);
        if(val==0) continue;//没有出现这个值
        if(val==1) //在第1段出现了,后面有n-1个符号
        {
            sum=qmi(2,n-1);
        }
        else //后面有n-val个符号，前面有3^(val-2)个集合
        {
            sum=qmi(2,n-val+1)*qmi(3,val-2)%mod;
            sum%=mod;
        }
        res+=sum;
        res%=mod;
    }
    cout<<res<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

总结：
思路很巧妙，首先是枚举每个值的贡献，然后找到了规律，下次做题的时候线分析每个题有啥好规律，然后根据规律做题。
再就是线段树的这个思路，感觉很巧妙，通过设置每一段的值，假设这一段出现过，那值就不是0，可以更新一次，否则，就是没出现过，值就是0。