踐踏---離散化+樹狀數組+差分

題目連結

區間修改和區間查詢分别通過差分轉變為 單點修改和單點查詢

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
#define int long long
const int N = 300010;
int n,k;
int tr[N];
vector<int>vec;
struct node
{
    int op,l,r,x;
}a[N];
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int v)
{
    for(int i=x;i<N;i+=lowbit(i))tr[i]+=v;
}
int query(int x)
{
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i))res+=tr[i];
    return res;
}
int get_id(int x)
{
    return lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1;
}

void modify(int l,int r,int v)
{
    if(r-l+1>=k)
    {
        add(1,v);
        add(k+1,-v);
    }
    else
    {
        l=(l%k)+1,r=(r%k)+1;
        if(l<=r)
        {
            add(l,v);
            add(r+1,-v);
        }
        else
        {
            add(l,v);
            add(k+1,-v);
            add(1,v);
            add(r+1,-v);
        }
    }
}

signed main()
{
    cin>>n>>k;
    if(n==0)
    {
        cout<<"fafa\n";
        return 0;
    }
    int op,l,r,x;
    for(int i=1;i<=n;i++)
    {
        cin>>op;
        if(op==1||op==2)
        {
            cin>>l>>r;
            a[i]={op,l,r};
            vec.push_back(l);
            vec.push_back(r);
        }
        else
        {
            cin>>x;
            a[i].op=3,a[i].x=x;
            vec.push_back(x);
        }
    }
    
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    
    if(k==0)
    {
        for(int i=1;i<=n;i++)
        {
            if(a[i].op==1||a[i].op==2)
            {
                int l=get_id(a[i].l);
                int r=get_id(a[i].r);
                if(a[i].op==1)add(l,1),add(r+1,-1);
                else add(l,-1),add(r+1,1);
            }
            else
            {
                int x=get_id(a[i].x);
                cout<<query(x)<<'\n';
            }
        }
    }
    else 
    {
        for(int i=1;i<=n;i++)
        {
            
            if(a[i].op==1)modify(a[i].l,a[i].r,1);
            else if(a[i].op==2)modify(a[i].l,a[i].r,-1);
            else
            {
                int x=(a[i].x%k)+1;
                cout<<query(x)<<'\n';
            }
        }
    }
}