# Codeforces 1327F AND Segments
> https://codeforces.com/contest/1327/problem/F

題意為有長度$n$之序列$a$，其中$1 \le a_i \lt 2^k$，給$m$個條件$(l_i, r_i, x_i)$，表示在子陣列$[a_{l_i}, a_{r_i}]$ 裡全部的數AND後必須為$x_i$，求總共有多少個$a$滿足條件。$1 \le n \le 5 \times 10^5$，$1 \le k \le 30$，$0 \le m \le 5 \times 10^5$。

這題裡面有一個子問題困擾了我很久，筆記一下。

給條件index區間$[l, r]$裡全部的數AND後要等於$x$，於是很直覺的拆成每個bit來想，如果第$k$個bit等於$1$，那表示區間中的數在第$k$個bit都要是$1$；反之如果第$k$個bit等於$0$，那表示區間中的數在第$k$個bit至少有一個$0$。

於是問題分解成獨立的對於每個bit，有$m$個區間限制，第一類為限制都是$1$，第二類則是區間中至少要有一個$0$，答案為每個bit貢獻的乘積，這可以用DP來解決。

定義$dp(i)$為將第$i$個index放$0$且小於$i$的index都符合條件的方案總數(不考慮$i$之後的情況)，於是考慮怎麼轉移，對於第一類包括$i$之區間$dp(i)=0$，對於第二類區間想一下在$i$為$0$時必須由$\lt i$的哪邊轉移過來，對於已經包含$i$的區間已經可以隨便放，沒條件的也可隨便放，都可以轉移過來，於是考慮不包刮$i$的第二類區間，則轉移方程為：
\begin{array}{ll}
dp(i) = \sum_{k=最靠近i且不包含i的最靠近i的左區間}^{i-1} dp(k)。
\end{array}

最靠近$i$且不包含$i$的最靠近$i$的左區間怎麼快速計算讓我想了很久==(感覺用multiset就過不了)，於是我就爛，看了別人的code學了一些技巧，定義$L(i)$為在所有第二類右區間$\le i$的區間中最靠近的左區間，這樣的話$dp(i)$求和下界就是$L(i-1)$。最後算到$dp(n+1)$就是對於該bit的總數了。

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const ll Inf = 1e18;
const int mod = 998244353;
const int N = 5e5 + 5;

int n, k, m;
int l[N], r[N], x[N], L[N], one[N];
ll dp[N], pre[N];

void solve(){
    cin >> n >> k >> m;
    for(int i=1; i<=m; i++){
        cin >> l[i] >> r[i] >> x[i];
    }

    auto cal = [&](int kk){
        for(int i=0; i<=n+1; i++) dp[i] = pre[i] = L[i] = one[i] = 0;
        for(int i=1; i<=m; i++){
            if((x[i]>>kk) & 1){
                one[l[i]]++;
                one[r[i]+1]--;
            }
            else{
                L[r[i]] = max(L[r[i]], l[i]);
            }
        }

        for(int i=1; i<=n+1; i++){
            one[i] += one[i-1];
            L[i] = max(L[i-1], L[i]); 
        }

        dp[0] = pre[0] = 1;
        for(int i=1; i<=n+1; i++){
            if(!one[i]){
                dp[i] = pre[i-1];
                if(L[i-1] > 0) dp[i] = (dp[i] - pre[L[i-1] - 1] + mod) % mod;
            }
            pre[i] = (dp[i] + pre[i-1]) % mod;
        }
        
        return dp[n+1];
    };

    ll ans = 1;
    for(int i=0; i<k; i++){
        ans = (ans * cal(i)) % mod;
        if(!ans) break;
    }
    cout << ans << endl;
} 
 
 
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--)
    solve();
 
    return 0;
}

### 時間複雜度 ：$O(nk)$
###### tags: `dp`