践踏---离散化+树状数组+差分

题目链接

区间修改和区间查询分别通过差分转变为 单点修改和单点查询

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