P11843 Sol

· · 题解

首先，离散化然后把 M 个修改预处理出来，这个用异或就可以做。

   cin >> _n >> m >> q;
   rep(i, 1, m)
      cin >> ml[i] >> mr[i], 
      T[++n] = ml[i], 
      T[++n] = mr[i] + 1;
   rep(i, 1, q) 
      cin >> ql[i] >> qr[i] >> k[i], 
      T[++n] = ql[i], T[++n] = qr[i] + 1;    
   std::sort(T + 1, T + 1 + n);
   n = std::unique(T + 1, T + 1 + n) - T - 1;
 # define F(i) (std::lower_bound(T + 1, T + 1 + n, i) - T)
   T[n + 1] = _n + 1;
   rep(i, 1, m){
        ml[i] = F(ml[i]);mr[i] = F(mr[i] + 1) - 1;
        tag[ml[i]] ^= 1;tag[mr[i] + 1] ^= 1;}
   rep(i, 1, n) tag[i] ^= tag[i - 1];

考虑如何求答案。注意到一个区间的答案一定形如

11111\cdots00101001\\

即先满足有足够多的 1，不够时把剩余部分拉过来“凑数”。

这里有一个关键的性质：前面的 1 取的越多，后面的部分越难满足 k。这就是说：满足单调性，可以二分答案。

我们考虑二分一个分界点，使其满足在 [l,mid] 之间的 1 全取的情况下后面有足够的数字，而且位置编号最大。

得到分界点后，答案的串为前面部分的 1 加上 [l^{\prime},r]，r-l^{\prime}+1=k-cnt_{1}。

至于此处为什么从后面开始取，由于我们的取法，每个 1 都在可能的最靠前的位置，如果有 1 由于靠前未被取到，那么我们的分界点其实可以设置在这个 1，与二分结果矛盾。

然后有哈希把答案预处理就好了。

# include<bits/stdc++.h>
# define rep(i,a,b) for(int i = (a);i <= (b);i ++)
# define dwn(i,a,b) for(int i = (a);i >= (b);i --)
# define fid(i,a,F) for(int i = (a);F;i ++)
# define int32 int
# define int64 long long
# define int16 short
# define dbg(x) std::cerr << #x << ":" << x <<"\n"
# define FaILurEg(s) std::freopen(s".in","r", stdin);std::freopen(s".out","w",stdout);
# define ___main signed main()
# define int long long
using std::cin;using std::cout;
int _n, n, m, q;
int ml[200005], mr[200005], ql[200005], qr[200005], k[200005];
int T[800005], tag[800006], c1[800005], c2[800005];int64 b[800005];
template<int mod>
    inline int64 qpow(int64 x, int64 y) {
        //assert(y >= 0);
        if(y == 0) return 1;
        if(y == 1) return x % mod;
        int64 m = qpow<mod>(x, y >> 1);
        return m * m % mod * (y & 1 ? x : 1) % mod;
    }
___main {//FaILurEg("bestsub");
const int mod = 1000000007;
   std::ios::sync_with_stdio(0);cin.tie(0);
   cin >> _n >> m >> q;
   rep(i, 1, m) cin >> ml[i] >> mr[i], T[++n] = ml[i], T[++n] = mr[i] + 1;
   rep(i, 1, q) cin >> ql[i] >> qr[i] >> k[i], T[++n] = ql[i], T[++n] = qr[i] + 1;    std::sort(T + 1, T + 1 + n);n = std::unique(T + 1, T + 1 + n) - T - 1;
 # define F(i) (std::lower_bound(T + 1, T + 1 + n, i) - T)
    T[n + 1] = _n + 1;
    rep(i, 1, m){
          ml[i] = F(ml[i]);mr[i] = F(mr[i] + 1) - 1;
          tag[ml[i]] ^= 1;tag[mr[i] + 1] ^= 1;}
    rep(i, 1, n) tag[i] ^= tag[i - 1], 
    c1[i] = c1[i - 1] + tag[i] * (T[i + 1] - T[i]), 
    c2[i] = c2[i - 1] + (T[i + 1] - T[i]) 
   //,assert(T[i + 1] - T[i]?1:(std::cerr << T[i] << " " << T[i + 1] << "\n" ,0))
   ,b[i] = b[i - 1] * qpow<mod>(2, T[i + 1] - T[i]) + tag[i] * (qpow<mod>(2, T[i + 1] - T[i]) + mod - 1) % mod, b[i] %= mod
    ;
   rep(i, 1, q) {
      ql[i] = F(ql[i]);qr[i] = F(qr[i] + 1) - 1;
      int l = ql[i] - 1, r = qr[i], ans = 0;
      if(c1[qr[i]] - c1[ql[i] - 1] >= k[i]) {
        cout << (qpow<mod>(2, k[i]) + mod - 1) % mod << "\n";continue;
      }
      while(l <= r) {
        int mid = (l + r) >> 1;
        //check
        bool F = (c2[qr[i]] - c2[mid] < k[i] - (c1[mid] - c1[ql[i] - 1]));
        if(!F) ans = std::max(ans, mid), l = mid + 1;
        else r = mid - 1;
      }
      int R = k[i] - (c1[ans] - c1[ql[i] - 1]);
      //std::cerr<<"Q" << ql[i] << " " << qr[i] << " " << ans << "\n";
      assert(!tag[ans + 1]);
      int64 out = (qpow<mod>(2, c1[ans] - c1[ql[i] - 1]) + mod - 1) % mod, 
      out2 = (b[qr[i]] - b[ans] * qpow<mod>(2, T[qr[i] + 1] - T[ans + 1]) % mod + mod) % mod;
      0;
      //std::cerr << b[ans] - b[ql[i] - 1] * qpow<mod>(2, T[ans + 1] - T[ql[i]]) << "\n";
      //rep(j, ans + 2, qr[i])
      //    out2 = out2 * qpow<mod>(2, T[j + 1] - T[j]) + tag[j] * (qpow<mod>(2, T[j + 1] - T[j]) + mod - 1) % mod, out2 %= mod;
      cout << (out * qpow<mod>(2, R) + out2) % mod << "\n";
   }    
}