526互联

AcWing,第110场周赛 智商药

发布时间 2023-07-02 17:43:42作者: magicat

AcWing,第110场周赛 智商药

tag：树状数组， 线段树，二维数点（因为有 \(r\) 这个限制，算吧）

分析：当吃药时 \(r\) 时，只有 \([l, r - 1]\) 的方法对答案有贡献，不难看出

\[dp_r = \sum_{i = l}^{r - 1}dp_i \]

问题转为求一段区间和，发现可以用树状数组和线段树去做，线段树代码太长弃之

再发现数据范围 \(1≤n≤10^9\) ， \(0≤l_i<r_i≤n\) ，使用离散化

剩下的细节，将 $ l- 1 , r - 1 ，0 ，n ，n - 1 $ 也要离散化，记得取模，板子的树状数组大小要开的够大，本来 \(15\) 分钟写完，段错误打完abc补题才发现板子的数组开小了T c[N]; 改了大小然后就过了?

//  AC one more times

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 1e9 + 7;
const int N = 2e5 + 10;


int m, n;
vector<int> vx;

template<class T>
struct BIT {
    T c[N * 4];
    int size;
    void resize(int s) { size = s;}
    T query(int x) { // 1 ... x
        assert(x <= size);
        T s = 0;
        for (; x; x -= x & (-x)) {
            s += c[x];
            s %= mod;
        }
        return s;
    }

    void modify(int x, T s) { // a[x] += s
        assert(x != 0);
        for (; x <= size; x += x & (-x)) {
            c[x] += s;
            c[x] %= mod;
        }
    } 
};

BIT<ll> tr;  

vector<pair<int, int>> e[N * 4];

void solve()
{       
    cin>>m>>n;
    vector<pair<int, int>> a(n);
    for(int i = 1; i <= n; i++)
    {
        cin>>a[i - 1].first>>a[i - 1].second;
        vx.push_back(a[i - 1].first - 1);
        vx.push_back(a[i - 1].second);  
        vx.push_back(a[i - 1].second - 1);  
    }
    vx.push_back(0);    vx.push_back(m);    vx.push_back(m - 1);

    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());

    sort(a.begin(), a.end());

    int nn = vx.size();
    tr.resize(nn);
    tr.modify(lower_bound(vx.begin(), vx.end(), 0) - vx.begin() + 1, 1);

    for(int i = 1; i <= n; i++)
    {
        int l = a[i - 1].first, r = a[i - 1].second;
        int p = lower_bound(vx.begin(), vx.end(), r) - vx.begin() + 1;
        e[p].push_back({l, r});
    }
    for(int i = 1; i <= nn; i++)
    {
        for(auto &it : e[i])
        {
            int l = it.first, r = it.second;
            ll t1 = 0, t2 = 0;
            if(l >= 1)
                t1 = tr.query(lower_bound(vx.begin(), vx.end(), l - 1) - vx.begin() + 1);
            t2 = tr.query(lower_bound(vx.begin(), vx.end(), r - 1) - vx.begin() + 1);
            ll t = (t2 - t1) % mod;
            if(t < 0)
                t += mod;       
            tr.modify(lower_bound(vx.begin(), vx.end(), r) - vx.begin() + 1, t);
        }
    }
        
    ll res = tr.query(lower_bound(vx.begin(), vx.end(), m) - vx.begin() + 1) - tr.query(lower_bound(vx.begin(), vx.end(), m - 1) - vx.begin() + 1);
    res %= mod;
    if(res < 0)
        res += mod;
    cout<<res<<'\n';

    return;
}


  
int main()
{
    std::ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int TC = 1;
    
    //cin >> TC;    
    for(int tc = 1; tc <= TC; tc++)
    {
        //cout << "Case #" << tc << ": ";         
        solve();
    }


    return 0;
}