记录编号	606198	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4174.[USACO25 Feb Gold]The Best Subsequence	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	9.080 s
提交时间	2025-09-18 21:35:46	内存使用	7.55 MiB

#include<iostream>
#include<set>
using namespace std;

typedef long long ll;
const int MAXN = 4e5 + 5;
const int B = 35000;
const int MOD = 1e9 + 7;

struct node{
    int l, r;
}s[MAXN];

int n, m, q;
int cnt = 0;
int pre[MAXN], h[MAXN];
int spw[B], bpw[B];
set<int> st;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    spw[0] = bpw[0] = 1;
    for(int i = 1; i < B; i ++){
        spw[i] = (spw[i - 1] << 1);
        if(spw[i] >= MOD) spw[i] -= MOD;
    }
    int base = (spw[B - 1] << 1);
    if(base >= MOD) base -= MOD;
    for(int i = 1; i < B; i ++){
        bpw[i] = 1ll * bpw[i - 1] * base % MOD;
    }
    auto qpow = [&](int t) -> int{
        return 1ll * bpw[t / B] * spw[t % B] % MOD;
    };
    auto ins = [&](int x){
        if(st.count(x))	st.erase(x);
		else st.insert(x);
    };
    auto Get_1 = [&](int x) -> int{
        int l = 0, r = cnt, mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(x >= s[mid].r) l = mid + 1;
            else r = mid;
        }
        if(l == cnt || x <= s[l].l) return pre[l];
        return pre[l] + x - s[l].l;
    };
    auto Get_hash = [&](int x) -> int{
        int l = 0, r = cnt, mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(x >= s[mid].r) l = mid + 1;
            else r = mid;
        }
        int lst = (l == 0) ? 0 : s[l - 1].r;
        if(l == cnt || x <= s[l].l){
            return 1ll * h[l] * qpow(x - lst) % MOD;
        }
        int p1 = 1ll * h[l] * qpow(x - lst) % MOD;
        int p2 = (qpow(x - s[l].l) - 1 + MOD) % MOD;
        return (p1 + p2) % MOD;
    };
    cin >> n >> m >> q;
    for(int i = 0; i < m; i ++){
        int l, r; cin >> l >> r;
        l --; ins(l); ins(r);
    }
    cnt = 0;
    while(!st.empty()){
        int l = *st.begin(); st.erase(st.begin());
        int r = *st.begin(); st.erase(st.begin());
        s[cnt ++] = {l, r};
    }
    int lst = 0;
    for(int i = 0; i < cnt; i ++){
        pre[i + 1] = pre[i] + s[i].r - s[i].l;
        int sz_0 = s[i].r - lst;
        int hs_1 = (qpow(s[i].r - s[i].l) - 1 + MOD) % MOD;
        h[i + 1] = (1ll * h[i] * qpow(sz_0) + hs_1) % MOD;
        lst = s[i].r;
    }
    while(q --){
        int l, r, k;
        cin >> l >> r >> k;
        l --;
        int pre_1 = Get_1(l);
        int ll = 0, rr = k;
        while(ll < rr){
            int mid = (ll + rr) >> 1;
            if(Get_1(r - mid) - pre_1 + mid >= k){
                rr = mid;
            }
			else {
                ll = mid + 1;
            }
        }
        int p1 = 1ll * (qpow(k - ll) - 1 + MOD) % MOD * qpow(ll) % MOD;
        int hr = Get_hash(r), hrl = Get_hash(r - ll);
        int p2 = (hr - 1ll * hrl * qpow(ll) % MOD + MOD) % MOD;
        cout << (p1 + p2) % MOD << '\n';
    }
    return 0;
}