看到这种题，我们肯定会想到\((x,y)\)一定有循环

我们要找到循环节的长度

推一下发现\(x\)的循环节长为\(\frac{AB}{B+1}\)。等一下，\(t\)是整数，所以循环节长为\(\frac{AB}{GCD(A,B+1)}\)

\(y\)的循环节长为\(B\)

所以\((x,y)\)的循环节长为\(lcm(\frac{AB}{GCD(A,B+1)},B)=\frac{AB}{GCD(A,B+1)}\)

对每个时间段对循环节长取模进行区间覆盖即可

代码（用了__int128）

#include 
    
     #define N 1000005#define ll long long#define getchar ncusing namespace std;inline char nc(){    static char buf[100000],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline ll read(){    register ll x=0,f=1;register char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();    return x*f;}inline void write(register ll x){    if(!x)putchar('0');if(x<0)x=-x,putchar('-');    static int sta[20];register int tot=0;    while(x)sta[tot++]=x%10,x/=10;    while(tot)putchar(sta[--tot]+48);}inline ll Max(register ll a,register ll b){    return a>b?a:b;}vector
     
      
        >v;int n;ll A,B;int main(){    n=read(),A=read(),B=read();    __int128 k=(__int128)A*B/__gcd(A,B+1);    for(register int i=1;i<=n;++i)    {        ll l=read(),r=read();        if(r-l+1>=k)        {            write((ll)k);            return 0;        }        else        {            l%=k;            r%=k;            if(l<=r)                v.push_back(make_pair(l,r));            else            {                v.push_back(make_pair(l,(ll)k-1));                v.push_back(make_pair(0ll,r));            }        }    }    sort(v.begin(),v.end());    ll l=0,r=-1,ans=0;    for(register int i=0;i
      
     
    

我们先考虑不带修改怎么做——珂以贪心地将桥的承受重量和车的重量从大到小排序，从大往小扫描车，用并查集维护边和答案

考虑有修改操作，我们珂以使用分块，设块的大小为\(blk\)

那么每个块中的修改操作不超过\(\frac{q}{blk}\)个

我们先把没有修改的边和所有询问的点像不带修一样从大到小排序，从大往小扫描车，对于每辆车，单独加入被修改的一些边，加入后通过并查集回退来撤销，所以并查集不能路径压缩，要按秩合并，处理完询问后要将原图更新，但是不能直接快排，新边要和原来已经有序的边进行合并排序，这个单块复杂度是\(O(m\alpha+\frac{n^2}{blk^2}\alpha+m)\)

我blk取的是\(\sqrt{n\log n}\)，所以总复杂度是\(O(m \sqrt{n\log n} \alpha)\)

#include 
    
     #define M 100005#define getchar ncusing namespace std;inline char nc(){    static char buf[100000],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int read(){    register int x=0,f=1;register char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();    return x*f;}inline void write(register int x){    if(!x)putchar('0');if(x<0)x=-x,putchar('-');    static int sta[20];register int tot=0;    while(x)sta[tot++]=x%10,x/=10;    while(tot)putchar(sta[--tot]+48);}struct edge{    int u,v,w,i;}e[M],E[M],tmp[M];bool operator < (edge a,edge b){    return a.w!=b.w?a.w>b.w:a.i
     
      b.b;}int fa[M],sz[M],top;struct mste{    int u,v;}sta[M];inline int getfa(register int x){    return x==fa[x]?x:getfa(fa[x]);}inline void Merge(register int u,register int v){    u=getfa(u);    v=getfa(v);    if(u==v)        return;    if(sz[u]
      
       =tmp2[i].b)        {            if(!vis[e[p].i])                Merge(e[p].u,e[p].v);            ++p;        }        int lastop=top;        for(register int j=1;j<=t1;++j)            d[tmp1[j].b]=e[id[tmp1[j].b]].w;        for(register int j=1;j<=t1;++j)            if(tmp1[j].id
       
        =tmp2[i].b)                Merge(e[id[tmp1[j].b]].u,e[id[tmp1[j].b]].v);        ans[tmp2[i].id]=sz[getfa(tmp2[i].r)];        while(top>lastop)            cancel();    }    for(register int i=1;i<=t1;++i)        e[id[tmp1[i].b]].w=tmp1[i].r;    t1=t2=0;    for(register int i=1;i<=m;++i)        if(vis[e[i].i])            E[++t1]=e[i];        else            e[++t2]=e[i];    sort(E+1,E+1+t1);    merge(E+1,E+1+t1,e+1,e+1+t2,tmp+1);    for(register int i=1;i<=m;++i)        e[i]=tmp[i];}int main(){    n=read(),m=read();    blk=sqrt(n*log2(n));    for(register int i=1;i<=m;++i)        e[i].u=read(),e[i].v=read(),e[i].w=read(),e[i].i=i;    sort(e+1,e+1+m);    Q=read();    for(register int i=1;i<=Q;++i)    {        int t=read();        if(t==1)        {            int b=read(),r=read();            q[++tot]=(query){i,t,b,r};        }        else        {            int s=read(),w=read();            q[++tot]=(query){i,t,w,s};        }        if(tot==blk)            work(),tot=0;    }    if(tot)        work();    for(register int i=1;i<=Q;++i)        if(ans[i])            write(ans[i]),puts("");     return 0;}
       
      
     
    

这道题珂以暴力数据结构

我们用树状数组套主席树

每个点开个主席树，每个位置表示假如之后再也不修改，能到那个位置的次数（包括修改前的次数）

树状数组维护主席树的和

这样就珂以方便的进行差分

上代码（不想说了，自己看，简单易懂）

注意主席树中存的是之后再也不修改的答案数，要根据情况判断是否要减去一些

#include 
    
     #define N 300005#define getchar ncusing namespace std;inline char nc(){    static char buf[100000],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int read(){    register int x=0,f=1;register char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();    return x*f;}inline void write(register int x){    if(!x)putchar('0');if(x<0)x=-x,putchar('-');    static int sta[20];register int tot=0;    while(x)sta[tot++]=x%10,x/=10;    while(tot)putchar(sta[--tot]+48);}int n,q,c[N];set
     
       st;set
      
       ::iterator now,pre,nxt;struct node{    int ls,rs,val;}tr[N*40];int tot,rt[N];inline void change(register int &x,register int l,register int r,register int pos,register int val){    if(!x)        x=++tot;    tr[x].val+=val;    if(l==r)        return;    int mid=l+r>>1;    if(pos<=mid)        change(tr[x].ls,l,mid,pos,val);    else        change(tr[x].rs,mid+1,r,pos,val);       }inline int querys(register int x,register int l,register int r,register int L,register int R){    if(!x)        return 0;    if(L<=l&&r<=R)        return tr[x].val;    int mid=l+r>>1,res=0;    if(L<=mid)        res+=querys(tr[x].ls,l,mid,L,R);    if(R>mid)        res+=querys(tr[x].rs,mid+1,r,L,R);    return res;}inline int lowbit(register int x){    return x&(-x);}inline void modify(register int x,register int pos,register int val){    while(x<=n+1)        change(rt[x],1,n+1,pos,val),x+=lowbit(x);}inline int query(register int x,register int pos){    int res=0;    while(x)        res+=querys(rt[x],1,n+1,1,pos),x-=lowbit(x);    return res;}int main(){    n=read(),q=read();    for(register int i=1;i<=n;++i)    {        char ch=getchar();        while(ch!='0'&&ch!='1')            ch=getchar();        c[i]=ch-'0';    }    st.insert(0),st.insert(n+1);    modify(1,1,q);    for(register int i=1,j=0;i<=n;++i)    {        if(c[i]==1)            continue;        st.insert(i);        modify(j+1,i+1,-q);        modify(i+1,i+1,q);        j=i;    }    while(q--)    {        char ch=getchar();        while(ch!='t'&&ch!='q')            ch=getchar();        if(ch=='t')        {            int x=read(),v=(c[x]==0)?1:-1;            if(c[x]==1)                st.insert(x);            now=st.find(x);            pre=nxt=now;            --pre,++nxt;            modify(*pre+1,x+1,q*v);            modify(x+1,x+1,-q*v);            if(*nxt!=n+1)            {                modify(*pre+1,*nxt+1,-q*v);                modify(x+1,*nxt+1,q*v);                         }            if(c[x]==0)                st.erase(x);            c[x]^=1;        }        else        {            int a=read(),b=read();            write(query(a,b)-q*(st.lower_bound(a)==st.lower_bound(b))),puts("");        }    }    return 0;}