rt.TLE on #10。不知道是代码常数太大还是哪写挂了。

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

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

const int N = 1e6 + 10,mod = 1e9 + 7;
long long n,q,x,y,z,l,r,opt,a[N];

long long quickpow(long long c,long long n,long long m)
{
	long long res = 1;
	while(n)
	{
		if(n & 1) res = res * c % m;
		c = c * c % m;
		n >>= 1;
	}	
	return res;
}

struct FHQ
{

long long tot,root;
long long son[N][2],size[N],dat[N],sum[N],val[N],bin[N],cov[N];

void pushup(long long p)
{
    size[p] = size[son[p][0]] + size[son[p][1]] + 1;
    sum[p] = (sum[son[p][0]] + sum[son[p][1]] + val[p]) % mod;
    bin[p] = (bin[son[p][0]] + bin[son[p][1]] + val[p] * val[p] % mod) % mod;
}

void cover(long long p,long long k)
{
    k %= mod;
    cov[p] = k;
    bin[p] = size[p] * k % mod * k % mod;
    sum[p] = k * size[p] % mod;
    val[p] = k;
}

void pushdown(long long p)
{
    if(cov[p] == -1) return;
    if(son[p][0]) cover(son[p][0],cov[p]);
    if(son[p][1]) cover(son[p][1],cov[p]);
    cov[p] = -1;
}

void split(long long p,long long k,long long &x,long long &y)
{
    if(p == 0) {x = y = 0;return;}pushdown(p);
    if(size[son[p][0]] < k) x = p,split(son[p][1],k - size[son[p][0]] - 1,son[p][1],y);
    else y = p,split(son[p][0],k,x,son[p][0]);
    pushup(p);
}

long long merge(long long u,long long v)
{
    if(u == 0 || v == 0) return u + v;
    if(dat[u] < dat[v])
    {
        pushdown(u);
        son[u][1] = merge(son[u][1],v);
        pushup(u);
        return u;
    }
    else
    {
        pushdown(v);
        son[v][0] = merge(u,son[v][0]);
        pushup(v);
        return v;
    }
}

long long New(long long v)
{
    size[++tot] = 1,dat[tot] = rand();
    sum[tot] = bin[tot] = val[tot] = v;
    cov[tot] = -1;
    return tot;
}

long long build(long long l,long long r)
{
    if(l > r) return 0;
    long long mid = l + r >> 1;
    long long k = New(a[mid]);
    son[k][0] = build(l,mid - 1);
    son[k][1] = build(mid + 1,r);
    pushup(k);
    return k;
}

long long Query_sum(long long l,long long r)
{
    split(root,r,x,z);
    split(x,l - 1,x,y);
    long long tmp = sum[y];
    root = merge(merge(x,y),z);
    return tmp;
}

long long Query_bin(long long l,long long r)
{
    split(root,r,x,z);
    split(x,l - 1,x,y);
    long long tmp = bin[y];
    root = merge(merge(x,y),z);
    return tmp;
}

void Cov(long long l,long long r,long long k)
{
    split(root,r,x,z);
    split(x,l - 1,x,y);
    cover(y,k);
    root = merge(merge(x,y),z);
}

void print(long long p)
{
    if(son[p][0]) print(son[p][0]);
    cout << val[p] << " ";
    if(son[p][1]) print(son[p][1]);
}

}tree;

int main()
{
    // freopen("input.in","r",stdin);
    n = read(),q = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    tree.root = tree.build(1,n);
    while(q--)
    {
        opt = read(),l = read(),r = read();
        if(opt == 1) tree.Cov(l,l,r);
        if(opt == 2) 
        {
            long long tmp = tree.Query_sum(l,r);
            if(r - l + 1 < 0) return 0;
            cout << (((r - l + 1) * tree.Query_bin(l,r) % mod - tmp * tmp % mod) % mod + mod) % mod * quickpow((r - l + 1) * (r - l + 1) % mod,mod - 2,mod) % mod << endl;
        }
        // tree.print(tree.root),cout << endl;
    }
    return 0;
}