践踏

题意：
1操作 加一条线段
2操作 删一条线段
3查询 有多少条线段满足x+kt（t是整数）

传送门

考虑在模k意义下，每条线段都是1到2个区间，如果这条线段的长度大于k的话，那么区间[0，k-1]就满足题意。
树状数组维护区间和，单点查询即可。
当k=0的时候，则判断有多少个线段经过某个点，离散化，树状数组维护。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int MOD=1e9+7;
typedef long long ll;

int tree[MAXN],up;
vector<int> vec;
pair<pair<int,int>,int> a[MAXN];
int T;

void add(int x,int a)
{
    while(x<=up) tree[x]+=a,x+=x&(-x);
}

int sum(int x)
{
    int res=0;
    while(x) res+=tree[x],x-=x&(-x);
    return res;
}

int main()
{
    int n,k,op,l,r;
    scanf("%d%d",&n,&k);
    if(n==0)
    {
        printf("fafa\n");
        return 0;
    }
    if(k)
    {
        up=k;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&op);
            if(op==1)
            {
                scanf("%d%d",&l,&r);
                if(r-l+1>=k)
                {
                    add(1,1);           //[1,k-1]
                    add(k+1,-1);
                    continue;
                }
                l=(l%k)+1;
                r=(r%k)+1;
                if(l<=r) {add(l,1); add(r+1,-1);}       //一条线段[l,r]
                else {
                    add(1,1);               //两条线段[1,r]和[l,k+1]
                    add(r+1,-1);
                    add(l,1);
                    add(k+1,-1);
                }
            }
            else if(op==2)          //删除线段则是添加的逆操作
            {
                scanf("%d%d",&l,&r);
                if(r-l+1>=k)
                {
                    add(1,-1);
                    add(k+1,1);
                    continue;
                }
                l=(l%k)+1;
                r=(r%k)+1;
                if(l<=r){
                    add(l,-1); add(r+1,1);
                }
                else {
                    add(1,-1);
                    add(r+1,1);         
                    add(l,-1);
                    add(k+1,1);
                }
            }
            else
            {
                scanf("%d",&l);
                printf("%d\n",sum(l%k+1));
            }
        }
    }
    else{
        up=2*n;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&a[i].second,&a[i].first.first);
            vec.push_back(a[i].first.first);
            if(a[i].second<=2)
            {
                scanf("%d",&a[i].first.second);
                vec.push_back(a[i].first.second);
            }
        }
        sort(vec.begin(),vec.end());
        vec.erase(unique(vec.begin(),vec.end()),vec.end()); //离散化
        for(int i=1;i<=n;i++)
        {
            if(a[i].second==1)          //离散化后，二分查询所需l,r
            {
                l=lower_bound(vec.begin(),vec.end(),a[i].first.first)-vec.begin()+1;
                r=lower_bound(vec.begin(),vec.end(),a[i].first.second)-vec.begin()+1;
                add(l,1);
                add(r+1,-1);
            }
            else if(a[i].second==2)
            {
                l=lower_bound(vec.begin(),vec.end(),a[i].first.first)-vec.begin()+1;
                r=lower_bound(vec.begin(),vec.end(),a[i].first.second)-vec.begin()+1;
                add(l,-1);
                add(r+1,1);
            }
            else{
                int x=lower_bound(vec.begin(),vec.end(),a[i].first.first)-vec.begin()+1;
                printf("%d\n",sum(x));
            }
        }
    }
    return 0;
}