P11843 Sol

首先，离散化然后把

M

个修改预处理出来，这个用异或就可以做。

CPP

   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

，与二分结果矛盾。

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

CPP

# 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";
   }	
}

文章操作

相关推荐

评论

P11843 Sol