#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10;

int n;
ll arr[N];

int main()
{
    int t;
    scanf("%d",&t);
    for(int T=1;T<=t;T++)
    {
        printf("Case #%d:\n",T);
        scanf("%d",&n);
        memset(arr,0,sizeof arr);
        for(int i=0;i<n;i++) scanf("%lld",&arr[i]);
        int k=0;
        for(int i=62;i>=0;i--)//求解线性基
        {
            for(int j=k;j<n;j++)
                if(arr[j]>>i&1)
                {
                    swap(arr[j],arr[k]);
                    break;
                }
            if(!(arr[k]>>i&1)) continue;
            for(int j=0;j<n;j++)
                if(j!=k&&(arr[j]>>i&1))
                    arr[j]^=arr[k];
            k++;
            if(k==n) break;
        }
        reverse(arr,arr+k);//我们的线性基是反着求的，0是最高位 
        int q;
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            ll x;
            scanf("%lld",&x); 
            if(k<n) x--;
            if(x>=(1ll<<k))
            {
                printf("-1\n");
                continue;
            }
            ll ans=0;
            for(int j=0;j<k;j++)
                if(x>>j&1) ans^=arr[j];
            printf("%lld\n",ans);
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10;

int n;
ll a[N];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%lld",&a[i]);

    int k=0;
    for(int i=62;i>=0;i--)//高斯消元求线性基
    {
        for(int j=k;j<n;j++)
            if(a[j]>>i&1) 
                {swap(a[j],a[k]); break;}
        if(!(a[k]>>i&1)) continue;
        for(int j=0;j<n;j++)
            if(j!=k&&(a[j]>>i&1))
                a[j]^=a[k];
        k++;
        if(k==n) break;
    }
    ll res=0;
    for(int i=0;i<n;i++)  res^=a[i];//答案将所有的线性基异或起来
    printf("%lld",res);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;

int n,m;
struct Query
{
    int l,r,id;
} Q[N];
int poi[N],cnt[N];
vector<int> nums;
ll ans[N];
int block;

inline int get(int x)
{
    return x/block;
}

bool cmp(Query a,Query b)
{
    int al=get(a.l),bl=get(b.l);
    if(al!=bl) return al<bl;
    return a.r<b.r;
}

void add(int &x,ll &res)
{
    cnt[x]++;
    res=max(res,(ll)cnt[x]*nums[x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&poi[i]),nums.push_back(poi[i]);
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++) poi[i]=lower_bound(nums.begin(),nums.end(),poi[i])-nums.begin();
    for(int i=1;i<=m;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        Q[i]=(Query){l,r,i};
    }
    block=max(10,(int)sqrt(n));
    sort(Q+1,Q+1+m,cmp);

    for(int x=1;x<=m;)
    {
        int y=x;
        while(y<=m && get(Q[y].l)==get(Q[x].l)) y++;
        int right=get(Q[x].l)*block+block-1;

        /*处理块内询问*/
        while(x<y && Q[x].r<=right)
        {
            ll res=0;
            int id=Q[x].id,l=Q[x].l,r=Q[x].r;
            for(int k=l;k<=r;k++) add(poi[k],res);
            ans[id]=res;
            for(int k=l;k<=r;k++) --cnt[poi[k]];
            ++x;
        }

        /*处理块外的询问*/
        ll res=0;
        int l=right+1,r=right;
        while(x<y)
        {
            int id=Q[x].id,ll=Q[x].l,rr=Q[x].r;
            while(r<rr) add(poi[++r],res);
            long long backup_=res;
            while(l>ll) add(poi[--l],res);
            ans[id]=res;
            while(l<right+1) --cnt[poi[l++]];
            res=backup_;
            ++x;
        }
        memset(cnt,0,sizeof cnt);
    }
    for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N=5e6+10;

void swap_(int &x,int &y)
{
    if(x!=y) x^=y^=x^=y;
}
#define swap swap_

int n,m;
int poi[N];
struct Query
{
    int l,r,no,cc;//左端点，右端点，编号，最近的一组修改
} Q[N];
struct Modif
{
    int l,c;
} M[N];
int qm=0,cm=0,block;
bool cmp(Query a,Query b)
{
    int al=a.l/2610,bl=b.l/2610;
    int ar=a.r/2610,br=b.r/2610;//cbrt(133333^2)≈2610
    if(al!=bl) return al<bl;
    if(ar!=br) return ar<br;
    return a.cc<b.cc;
}
int cnt[N],ans[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>poi[i];
    for(int i=1;i<=m;++i)
    {
        int a,b;
        char s;
        cin>>s>>a>>b;
        if(s=='Q')
            ++qm, Q[qm]=(Query){a,b,qm,cm};
        else M[++cm]=(Modif){a,b};
    }
    sort(Q+1,Q+1+qm,cmp);

    for(int i=1,l=1,r=0,t=0,res=0;i<=qm;++i)
    {
        int id=Q[i].no, ll=Q[i].l, rr=Q[i].r, tt=Q[i].cc;
        while(l<ll)
        {
            --cnt[poi[l]];
            if(!cnt[poi[l]]) --res;
            ++l;
        }
        while(l>ll) 
        {
            --l;
            if(!cnt[poi[l]]) ++res;
            ++cnt[poi[l]];
        }
        while(r<rr) 
        {
            ++r;
            if(!cnt[poi[r]]) ++res;
            ++cnt[poi[r]];
        }
        while(r>rr)
        {
            --cnt[poi[r]];
            if(!cnt[poi[r]]) --res;
            --r;
        }
        while(t<tt)
        {
            ++t;
            if(l<=M[t].l&&M[t].l<=r)
            {
                --cnt[poi[M[t].l]];
                if(!cnt[poi[M[t].l]]) --res;
                if(!cnt[M[t].c]) ++res;
                ++cnt[M[t].c];
            }
            swap(M[t].c,poi[M[t].l]);
        }
        while(t>tt)
        {
            if(l<=M[t].l&&M[t].l<=r)
            {
                --cnt[poi[M[t].l]];
                if(!cnt[poi[M[t].l]]) --res;
                if(!cnt[M[t].c]) ++res;
                ++cnt[M[t].c];
            }
            swap(M[t].c,poi[M[t].l]);
            --t;
        }
        ans[id]=res;
    }
    for(int i=1;i<=qm;++i)
        cout<<ans[i]<<'\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+10,M=2e6+10;

inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        if(ch=='-') w=-1,ch=getchar();
        else ch=getchar();
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-48,ch=getchar();
    return s*w;
}

int n;
int head[N],ver[M],nxt[M],tot=0;
bool rm[M];//标记被删掉的边
void add(int x,int y)
{
    ver[tot]=y;
    nxt[tot]=head[x];
    head[x]=tot++;
}

int poi[N];
bool vis[N],ins[N];
ll f1[N][2],f2[N][2];//省一点清空的时间
ll ans=0;

void dfs_f(int x,int w,ll f[][2])
{
    f[x][0]=0;
    if(x!=w) f[x][1]=poi[x];
    for(int i=head[x];~i;i=nxt[i])
    {
        if(rm[i]) continue;
        int y=ver[i];
        dfs_f(y,w,f);
        f[x][0]+=max(f[y][0],f[y][1]);
        if(x!=w) f[x][1]+=f[y][0];
    }
}

void dfs_c(int x,int from)
{
    vis[x]=ins[x]=1;
    for(int i=head[x];~i;i=nxt[i])
    {
        int y=ver[i];
        if(!vis[y]) dfs_c(y,i);
        else if(ins[y])
        {
            rm[i]=1;//删边
            dfs_f(y,-1,f1);
            dfs_f(y,x,f2);
            ans+=max(f1[y][0],f2[y][1]);
        }
    }
    ins[x]=0;
}

int main()
{
    n=read();
    memset(head,-1,sizeof head);
    for(int i=1;i<=n;i++)
    {
        poi[i]=read();
        add(read(),i);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs_c(i,-1);
    printf("%lld",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e7+10,M=2e7+20;

int n;
int head[N],ver[M],nxt[M],edg[M],tot=0;
void add(int x,int y,int z)
{
    ver[tot]=y; edg[tot]=z; nxt[tot]=head[x]; head[x]=tot++;
}
int fa[N],fw[N];//记录每一个节点的父亲，以及到父亲的权值
int cir[N],ed[N],cnt=0;//所有在环内的点，不同环的展开序列在 cir 中的终点，环的数量。
ll s[N],d[M],sum[M];//前缀和，破环为链后的dis，破环为链后的前缀和
bool vis[N],ins[N];//是否在栈内(dfs找环的时候用)
ll q[N],ans=0;//单个基环树的答案

void dfs_c(int x,int from)//当前节点，来源边
{
    vis[x]=ins[x]=1;
    for(int i=head[x];~i;i=nxt[i])
    {
        if(i==(from^1)) continue;
        int y=ver[i];
        fa[y]=x; fw[y]=edg[i];
        if(!vis[y]) dfs_c(y,i);
        else if(ins[y])//找到了重复的点
        {
            ++cnt;
            ed[cnt]=ed[cnt-1];
            ll sum=edg[i];
            for(int k=x;k!=y;k=fa[k])//往回跳，统计前缀和
            {
                s[k]=sum;
                sum+=fw[k];
                cir[++ed[cnt]]=k;
            }
            s[y]=sum,cir[++ed[cnt]]=y;//记得把这个重复点也加进去。
        }
    }
    ins[x]=0;
}

ll dfs_d(int x,int f)
{
    vis[x]=1;
    ll d1=0,d2=0;
    for(int i=head[x];~i;i=nxt[i])
    {
        int y=ver[i];
        if(vis[y]||y==f) continue;
        ll dis=dfs_d(y,x)+edg[i];
        if(dis>d1) d2=d1,d1=dis;
        else if(dis>d2) d2=dis;
    }
    ans=max(ans,d1+d2);//处理数的直径
    return d1;//返回到根节点的最大距离
}

int main()
{
    scanf("%d",&n);
    memset(head,-1,sizeof head);
    for(int i=1;i<=n;i++)
    {
        int a,L;
        scanf("%d%d",&a,&L);
        add(i,a,L); add(a,i,L);
    }
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs_c(i,-1);//找到所有的环
    memset(vis,0,sizeof vis);
    for(int i=1;i<=ed[cnt];i++) vis[cir[i]]=1;

    ll res=0;
    for(int i=1;i<=cnt;i++)
    {
        ans=0;
        int nn=0;//记录一下环的大小
        for(int j=ed[i-1]+1;j<=ed[i];j++)
        {
            int k=cir[j];
            d[nn]=dfs_d(k,k);//树形Dp搜直径
            sum[nn]=s[k];//记录前缀和
            ++nn;
        }
        for(int j=0;j<nn;j++)//破环为链
            d[nn+j]=d[j], sum[nn+j]=sum[j]+sum[nn-1];
        int hh=0,tt=-1;//单调队列
        for(int j=0;j<nn*2;j++)
        {
            while(hh<=tt && j-q[hh]>=nn) ++hh;
            if(hh<=tt) ans=max(ans,d[j]+sum[j]+d[q[hh]]-sum[q[hh]]);
            while(hh<=tt && d[q[tt]]-sum[q[tt]]<=d[j]-sum[j]) --tt;
            q[++tt]=j;
        }
        res+=ans;
    }
    printf("%lld",res);
    return 0;
}

题目链接 Acwing1082.恨7不成妻

疑似取模错误？有好心人能指出一下吗孩子快调疯了/kk

能过样例qwq

输入：

30
363694564656 363694564656281
2065 7880
2131 10966
613598582516 613598582516851
77182866 77182866186
3697752 3697752138
468 2411
333747343188 333747343188201
47068022 47068022246
580078972076 580078972076634
33724914 33724914608
62854748 62854748381
31582682830 31582682830590
2863 8337
60149260978 60149260978249
6728 13513
4080274 4080274700
992425761914 992425761914711
202262 202262221
1611598425 1611598425284
604227655123 604227655123205
90551433890 90551433890582
38611822 38611822566
890541741 890541741557
10516425 10516425702
6835 13126
709 4699
664217181876 664217181876773
276337573903 276337573903270
752393818352 752393818352349

输出：

-248150566
-521922161
-109621570
749423703
132227709
-776910657
276229203
-28919330
14141788
418921292
-643403660
316575026
739820166
44737798
336521959
782922328
-240076558
152405561
-21763115
-187688022
-911324664
-444422553
-384901693
104202848
451076435
111900541
-205128092
-369243597
206819515
-484243646

标答：

844499414
933604100
45044660
51969141
909197529
848156264
539073839
529861300
84635702
998215803
602529091
179796461
835438517
4302699
78657965
91488791
458810956
679140518
434855267
693261912
135926470
122748988
386701852
586130964
477301470
999984089
937536957
279088084
703078034
182860271

错误的代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+10;
const ll MOD=1e9+7;

ll mod(ll x,ll p) {return (x%p+p)%p;}

ll f[35][10][10][10];//平方和
ll g[35][10][10][10];//和
ll h[35][10][10][10];//个数
ll pow7[30],powm[30];

void init()
{
    for(int i=0;i<=9;i++) 
    {
        if(i==7) continue;
        f[1][i][mod(i,7)][mod(i,7)]+=i*i;
        g[1][i][mod(i,7)][mod(i,7)]+=i;
        h[1][i][mod(i,7)][mod(i,7)]++;
    }
    ll t=10;
    for(int i=2;i<=19;i++)
    {
        t=t*10;
        for(int j=0;j<=9;j++)
        {
            if(j==7) continue;
            for(int a=0;a<7;a++)
            {
                for(int b=0;b<7;b++)
                {
                    for(int k=0;k<=9;k++)
                    {
                        if(k==7) continue;
                        h[i][j][a][b]=mod(h[i][j][a][b]+h[i-1][k][mod(a-j,7)][mod(b-j*t,7)],MOD);

                        g[i][j][a][b]=mod(g[i][j][a][b]+mod(mod(h[i-1][k][mod(a-j,7)][mod(b-j*t,7)]*j*mod(t,MOD),MOD)+g[i-1][k][mod(a-j,7)][mod(b-j*t,7)],MOD),MOD);

                        f[i][j][a][b]=mod(f[i][j][a][b]
                                + mod(h[i-1][k][mod(a-j,7)][mod(b-j*t,7)]*mod(j*j*mod(mod(t,MOD)*mod(t,MOD),MOD),MOD),MOD)
                                + mod(mod(2*j*mod(t,MOD),MOD)*g[i-1][k][mod(a-j,7)][mod(b-j*t,7)],MOD)
                                + mod(f[i-1][k][mod(a-j,7)][mod(b-j*t,7)],MOD),MOD);
                    }
                }
            }
        }
    }
    pow7[0]=powm[0]=1;
    for(int i=1;i<=20;i++)
    {
        pow7[i]=mod(pow7[i-1]*10,7);
        powm[i]=mod(powm[i-1]*10,MOD);
    }
}

ll dp(ll n)
{
    int nn=mod(n,MOD);
    if(n==0) return 0;
    vector<ll> nums;
    while(n>0) nums.push_back(n%10),n/=10;

    ll res=0,last=0,last2=0;
    for(int i=nums.size()-1;i>=0;i--)
    {
        ll x=nums[i];
        for(int j=0;j<x;j++)//再做一遍公式
        {
            if(j==7) continue;
            ll aa=mod(-last,7);
            ll bb=mod(-last2*pow7[i+1],7);
            ll ff=0,gg=0,hh=0;//平方和，和，个数

            for(int a=0;a<7;a++)
                for(int b=0;b<7;b++)
                {
                    if(a==aa||b==bb) continue;
                    ff=mod(ff+f[i+1][j][a][b],MOD);
                    gg=mod(gg+g[i+1][j][a][b],MOD);
                    hh=mod(hh+h[i+1][j][a][b],MOD);
                }

            res=mod(res 
             + mod(mod(mod((last2%MOD)*(last2%MOD),MOD)*mod(mod(powm[i+1],MOD)*mod(powm[i+1],MOD),MOD),MOD)*hh,MOD)
             + mod(mod(2*last2,MOD)*mod(powm[i+1]*gg,MOD),MOD)
             + mod(ff,MOD),MOD);
        }
        if(x==7) break;
        last+=x; last2=last2*10LL+x;

        if(!i&&mod(last,7)!=0&&mod(nn,7)!=0) res=mod(res+mod(mod(nn,MOD)*mod(nn,MOD),MOD),MOD);
    }
    return res;
}

int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",dp(r)-dp(l-1));
    }
    return 0;
}

双倍的树，$n^2$ 的调试难度

#include <bits/stdc++.h>
using namespace std;

const int N=1800010,INF=2147483647;

/*----------splay部分----------*/
struct Node1
{
    int s[2],p,v,size;

    void init(int _v,int _p)
    {
        v=_v,p=_p;
        size=1;
    }

} tree[N<<1];
int idx=0;

void push_up(int node)
{
    tree[node].size=tree[tree[node].s[0]].size+tree[tree[node].s[1]].size+1;
}

void rotate(int x)//旋转
{
    int y=tree[x].p, z=tree[y].p;
    int k=tree[y].s[1]==x;
    tree[z].s[tree[z].s[1]==y]=x; tree[x].p=z;//x代y做z儿子
    tree[y].s[k]=tree[x].s[k^1], tree[tree[x].s[k^1]].p=y;//x y 子树互换
    tree[x].s[k^1]=y, tree[y].p=x;//y 做 x 儿子
    push_up(y),push_up(x);
}

void splay(int &root,int x,int k)
{
    while(tree[x].p!=k)
    {
        int y=tree[x].p, z=tree[y].p;
        if(z!=k)
        {
            if((tree[y].s[1]==x)^(tree[z].s[1]==y)) rotate(x);//判断折线形
            else rotate(y);
        }
        rotate(x);
    }
    if(!k) root=x;
}

void insert(int &root,int v)//插入
{
    int u=root,p=0;
    while(u) p=u,u=tree[u].s[tree[u].v<v];
    u=++idx;
    if(p) tree[p].s[v>tree[p].v]=u;
    tree[u].init(v,p);
    splay(root,u,0);
}

int get_k(int &root,int v)//查找比 v 小的数的个数
{
    int u=root,res=0;
    while(u)
    {
        if(tree[u].v<v) res+=tree[tree[u].s[0]].size+1,u=tree[u].s[1];
        else u=tree[u].s[0];
    }
    return res;
}

int getPre(int &root,int v)//查找最大的比 v 小的数
{
    int u=root,res=-INF;
    while(u)
    {
        if(tree[u].v<v) res=max(res,tree[u].v),u=tree[u].s[1];
        else u=tree[u].s[0];
    }
    return res;
}

int getSuc(int &root,int v)//查找最小的比 v 大的数
{
    int u=root,res=INF;
    while(u)
    {
        if(tree[u].v>v) res=min(res,tree[u].v),u=tree[u].s[0];
        else u=tree[u].s[1];
    }
    return res;
}

void update(int &root,int x,int y)//插入函数
{
    int u=root;
    while(u)
    {
        if(tree[u].v==x) break;
        else if(tree[u].v>x) u=tree[u].s[0];
        else u=tree[u].s[1];
    }
    splay(root,u,0);
    int l=tree[u].s[0],r=tree[u].s[1];
    while(tree[l].s[1]) l=tree[l].s[1];
    while(tree[r].s[0]) r=tree[r].s[0];
    splay(root,l,0); splay(root,r,l);
    tree[r].s[0]=0;
    push_up(r),push_up(l);
    insert(root,y);
}

/*----------线段树部分----------*/
struct Node2
{
    int l,r;
    int root;
} tr1[N<<1];

int n,m;
int arr[N];

#define lnode node<<1
#define rnode node<<1|1

void build(int node,int l,int r)//建树
{
    tr1[node].l=l,tr1[node].r=r;
    insert(tr1[node].root,INF); insert(tr1[node].root,-INF);//插入哨兵节点
    for(int i=l;i<=r;i++) insert(tr1[node].root,arr[i]);
    if(l==r) return ;
    int mid=l+r>>1;
    build(lnode,l,mid); build(rnode,mid+1,r);
}

int getRank(int node,int l,int r,int x)//查找区间内比 x 小的个数
{
    if(l<=tr1[node].l&&tr1[node].r<=r) return get_k(tr1[node].root,x)-1;//记得减去哨兵节点
    int mid=tr1[node].l+tr1[node].r>>1;
    int res=0;
    if(l<=mid) res+=getRank(lnode,l,r,x);
    if(r>mid) res+=getRank(rnode,l,r,x);
    return res;
}

void change(int node,int pos,int x)//修改
{
    update(tr1[node].root,arr[pos],x);
    if(tr1[node].l==tr1[node].r) return ;
    int mid=tr1[node].l+tr1[node].r>>1;
    if(pos<=mid) change(lnode,pos,x);
    else change(rnode,pos,x);
}

int queryPre(int node,int l,int r,int x)//查找前驱
{
    if(l<=tr1[node].l&&tr1[node].r<=r) return getPre(tr1[node].root,x);
    int mid=tr1[node].l+tr1[node].r>>1;
    int res=-INF;
    if(l<=mid) res=max(res,queryPre(lnode,l,r,x));
    if(r>mid) res=max(res,queryPre(rnode,l,r,x));
    return res;
}

int querySuc(int node,int l,int r,int x)//查找后继
{
    if(l<=tr1[node].l && tr1[node].r<=r) return getSuc(tr1[node].root,x);
    int mid=tr1[node].l+tr1[node].r>>1;
    int res=INF;
    if(l<=mid) res=min(res,querySuc(lnode,l,r,x));
    if(r>mid) res=min(res,querySuc(rnode,l,r,x));
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    build(1,1,n);

    for(int i=1;i<=m;i++)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            int ans=getRank(1,l,r,x)+1;
            printf("%d\n",ans);
        }
        if(opt==2)
        {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            int L=0,R=1e8;
            while(L<R)
            {
                int mid=L+R+1>>1;
                if(getRank(1,l,r,mid)+1<=k) L=mid;
                else R=mid-1;
            }
            printf("%d\n",L);
        }
        if(opt==3)
        {
            int pos,x;
            scanf("%d%d",&pos,&x);
            change(1,pos,x);
            arr[pos]=x;
        }
        if(opt==4)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            int ans=queryPre(1,l,r,x);
            printf("%d\n",ans);
        }
        if(opt==5)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            int ans=querySuc(1,l,r,x);
            printf("%d\n",ans);
        }
    }
}

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+10,INF=1e8;

struct Node
{
    int l,r;
    multiset<int> s;//set(本质平衡树)维护当前的区间
} tree[N<<2];

int n,m;
int w[N];

#define lnode node<<1
#define rnode node<<1|1

void build(int node,int start,int end)//建树
{
    tree[node].l=start,tree[node].r=end;
    tree[node].s.insert(-INF),tree[node].s.insert(INF);//插入哨兵节点
    for(int i=start;i<=end;i++) tree[node].s.insert(w[i]);//将区间内的数逐个插入
    if(start==end) return ;
    int mid=start+end>>1;
    build(lnode,start,mid);
    build(rnode,mid+1,end);
}

void update(int node,int pos,int x)
{
    tree[node].s.erase(tree[node].s.find(w[pos]));//先将这个位置的数字删去
    tree[node].s.insert(x);//再插入我们想要的数字
    if(tree[node].l==tree[node].r) return ;
    int mid=tree[node].l+tree[node].r>>1;
    if(pos<=mid) update(lnode,pos,x);
    else update(rnode,pos,x);
}

int query(int node,int l,int r,int x)
{
    if(l<=tree[node].l&&tree[node].r<=r)//找对区间
    {
        auto its=tree[node].s.lower_bound(x);
        --its;//迭代器直接写了 auto，原本的迭代器名称又长又臭
        return *its;
    }
    int mid=tree[node].l+tree[node].r>>1,res=-INF;
    if(l<=mid) res=max(res,query(lnode,l,r,x));
    if(r>mid) res=max(res,query(rnode,l,r,x));
    return res;
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int opt;
        scanf("%d",&opt);
        if(opt==1)
        {
            int pos,x;
            scanf("%d%d",&pos,&x);
            update(1,pos,x);
            w[pos]=x;
        }
        if(opt==2)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            int ans=query(1,l,r,x);
            printf("%d\n",ans);
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e4+10;
int pr[N],tot=0,mu[N],sum[N];
bool mp[N];
ll h[N];

int get(int k,int x)//整除分块结论
{
    return k/(k/x);
}

void init(int n)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!mp[i]) mu[i]=-1,pr[++tot]=i;
        for(int j=1;pr[j]*i<=n;j++)
        {
            int tmp=pr[j]*i;
            mp[tmp]=1;
            if(i%pr[j]==0) break;
            mu[tmp]=-mu[i];

        }
    }
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+mu[i];

    for(int i=1;i<=n;i++)//预处理h(x)
    {
        for(int l=1,r;l<=i;l=r+1)
        {
            r=min(i,get(i,l));
            h[i]+=(r-l+1)*(i/l);
        }
    }
}

int main()
{
    init(N-10);//预处理h(x),mu(x)
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        ll res=0;
        int nn=min(n,m);
        for(int l=1,r;l<=nn;l=r+1)
        {
            r=min(nn,min(get(n,l),get(m,l)));
            res+=(ll)(sum[r]-sum[l-1])*h[n/l]*h[m/l];
        }
        printf("%lld\n",res);
    }
    return 0;
}