线段树进阶
目录未更新完!!!!!!
线段树板子:
#define lc u<<1
#define rc u<<1|1
const int N = 200005;
struct tree{
int l,r,su,tag;
}tr[N << 2];
void push_up(tree &u,tree l,tree r){
}
void build(int u,int l,int r){
tr[u] = {l,r,a[l],0};
if(l==r) return;
int mid = l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(tr[u],tr[lc],tr[rc]);
}
void calc(int u,int op){
tree& t = tr[u];
if(op==1){
}else{
}
}
void push_down(int u){
if(tr[u].tag == ?) calc(lc,?),calc(rc,?);
if(tr[u].tag == ?) calc(lc,?),calc(rc,?);
tr[u].tag = 0;
}
void update(int u,int l,int r,int op){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
calc(u,op);
return;
}
push_down(u);
if(l > tr[lc].r){
update(rc,l,r,op);
push_up(tr[u],tr[lc],tr[rc]);
return;
}
if(r < tr[rc].l){
update(lc,l,r,op);
push_up(tr[u],tr[lc],tr[rc]);
return;
}
update(lc,l,r,op);
update(rc,l,r,op);
push_up(tr[u],tr[lc],tr[rc]);
}
//合并查询
T quary(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return {} ;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u];
}
push_down(u);
if(l > tr[lc].r) return quary(rc,l,r); //在右半部分
if(r < tr[rc].l) return quary(lc,l,r); //在左半部分
T t;
push_up(t,quary(lc,l,r),quary(rc,l,r));//两个部分各占一点
return t;
}
线段树+贪心/线段树+排序
例题:
1.洛谷P1607 Fair Shuttle G
链接:
[P1607 USACO09FEB] Fair Shuttle G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
线段覆盖贪心问题,观察对比发现按 r时间顺序排序得到的答案明显更大,维护区间最大值即可,注意要做修改操作,因为中途奶牛上车会影响最大值
代码:
#define lc u<<1
#define rc u<<1|1
const int N = 20005;
struct node
{
int l,r,w;
bool operator<(const node &n1)const{
return r < n1.r;
};
};
struct tree{
int l,r,mx,add;
}tr[N << 2];
void push_up(int u){
tr[u].mx = max(tr[lc].mx,tr[rc].mx);
}
void push_down(int u){
tr[lc].add += tr[u].add;
tr[rc].add += tr[u].add;
tr[lc].mx += tr[u].add;
tr[rc].mx += tr[u].add;
tr[u].add = 0;
}
void build(int u,int l,int r){
tr[u] = {l,r,0,0};
if(l==r) return;
int mid = l + r >> 1;
build(lc,l,mid);
build(rc,mid + 1,r);
}
void update(int u,int l,int r,int v){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
tr[u].mx += v;
tr[u].add += v;
return;
}
push_down(u);
update(lc,l,r,v);
update(rc,l,r,v);
push_up(u);
}
int quary(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].mx;
}
push_down(u);
return max(quary(lc,l,r),quary(rc,l,r));
}
int n,m,c;
vector<node> a;
void solve(){
cin >> n >> m >> c;
build(1,1,m + 1);
for(int i = 1;i<=n;i++){
int l,r,w;
cin >> l >> r >> w;
a.push_back({l,r,w});
}
sort(a.begin(),a.end());
int ans = 0;
for(int i = 0;i < n;i++){
int l = a[i].l, r= a[i].r, w = a[i].w;
int mx = quary(1,l,r - 1);
int on = min(c - mx,w);
ans+=on;
update(1,l,r - 1,on);
}
cout << ans << endl;
}
2.洛谷P1937 Barn Allocation G
链接:
[P1937 USACO10MAR] Barn Allocation G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
线段覆盖贪心问题,观察对比发现按 r时间顺序排序得到的答案明显更优,对开始的数组建立线段树,表示当前各个区间的容量最小值,判断1头牛能否加入一个区间,加入则ans++,同时更新区间将区间容量-1;
代码:
#define lc u<<1
#define rc u<<1|1
const int N = 100005;
int a[N];
struct node{
int l,r;
bool operator<(const node & n1) const{
return r < n1.r;
}
};
struct tree{
int l,r,mi,add;
}tr[N << 2];
void push_up(int u){
tr[u].mi = min(tr[lc].mi,tr[rc].mi);
}
void push_down(int u){
tr[lc].add += tr[u].add;
tr[rc].add += tr[u].add;
tr[lc].mi -= tr[u].add;
tr[rc].mi -= tr[u].add;
tr[u].add = 0;
}
void build(int u,int l,int r){
tr[u] = {l,r,0x3f3f3f3f,0};
if(l==r){
tr[u] = {l,r,a[l],0};
return;
}
int mid = l + r >> 1;
build(lc,l,mid);
build(rc,mid + 1,r);
push_up(u);
}
void update(int u,int l,int r,int v){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
tr[u].mi -= v;
tr[u].add += v;
return;
}
push_down(u);
update(lc,l,r,v);
update(rc,l,r,v);
push_up(u);
}
int quary(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0x3f3f3f3f;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].mi;
}
push_down(u);
return min(quary(lc,l,r),quary(rc,l,r));
}
int n,m;
void solve(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
build(1,1,n);
vector<node> a;
for(int i = 1;i<=m;i++){
int l,r;
cin >>l >> r;
a.push_back({l,r});
}
sort(a.begin(),a.end());
int ans = 0;
for(int i = 0; i < m;i++){
int l = a[i].l, r = a[i].r;
int mi = quary(1,l,r);
if(mi <= 0){
continue;
}
ans++;
update(1,l,r,1);
}
cout << ans << endl;
}
3.洛谷P1972 HH的项链
链接:
[P1972 SDOI2009] HH的项链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
我们将在线询问改为离线,然后对r进行排序,然后顺序遍历数组,如果碰到之前出现过的数,把之前出现的最后一次的下标,单点修改-1,把当前下标+1,对每个r开个桶,然后线段树统计答案即可
代码:
#define lc u<<1
#define rc u<<1|1
const int N = 1000005;
struct node{
int l,r,id;
bool operator<(const node & n1) const{
return r < n1.r;
}
};
struct tree{
int l,r,su;
}tr[N << 2];
void push_up(int u){
tr[u].su = tr[lc].su+tr[rc].su;
}
void build(int u,int l,int r){
tr[u] = {l,r,0};
if(l==r) return;
int mid = l + r >> 1;
build(lc,l,mid);
build(rc,mid + 1,r);
}
void update(int u,int x,int v){
if(tr[u].l > x || tr[u].r < x) return;
if(tr[u].l == x && tr[u].r == x){
tr[u].su += v;
return;
}
update(lc,x,v);
update(rc,x,v);
push_up(u);
}
int quary(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].su;
}
return quary(lc,l,r) + quary(rc,l,r);
}
int n,m;
int a[N],last[N],ans[N];
vector<node> v[N];
vector<node> qs;
void solve(){
cin >> n;
build(1,1,n);
for(int i = 1;i<=n;i++){
cin >> a[i];
}
cin >> m;
for(int i = 1; i <= m;i++){
int l,r;
cin >> l >> r;
v[r].push_back({l,r,i});
sort(v[r].begin(),v[r].end());
}
for(int i = 1;i<=n;i++){
if(last[a[i]]){
update(1,last[a[i]],-1);
}
last[a[i]] = i;
update(1,i,1);
for(auto &p:v[i]){
ans[p.id] = quary(1,p.l,p.r);
}
}
for(int i =1;i<=m;i++){
cout << ans[i] << endl;
}
}
线段树+双指针
例题:
1.洛谷P1712 区间
链接:
[P1712 NOI2016] 区间 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1937)
思路:
对每个区间记录下来并且按区间长度排序,进行同向双指针,看数组区间内是否有一段长度(即最大长度,超过m,有就右指针不动,左指针不断右移,不断更新答案最小值)
代码:
#define lc u<<1
#define rc u<<1|1
const int N = 500005;
struct node{
int l,r,len;
bool operator<(const node & n1) const{
return len < n1.len;
}
};
struct tree{
int l,r,ma,add;
}tr[N*2 << 2];
void push_up(int u){
tr[u].ma = max(tr[lc].ma,tr[rc].ma);
}
void push_down(int u){
tr[lc].add += tr[u].add;
tr[rc].add += tr[u].add;
tr[lc].ma += tr[u].add;
tr[rc].ma += tr[u].add;
tr[u].add = 0;
}
void build(int u,int l,int r){
tr[u] = {l,r,0,0};
if(l==r) return;
int mid = l + r >> 1;
build(lc,l,mid);
build(rc,mid + 1,r);
push_up(u);
}
void update(int u,int l,int r,int v){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
tr[u].ma += v;
tr[u].add += v;
return;
}
push_down(u);
update(lc,l,r,v);
update(rc,l,r,v);
push_up(u);
}
int quary(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].ma;
}
push_down(u);
return max(quary(lc,l,r),quary(rc,l,r));
}
int n,m;
void solve(){
cin >> n >> m;
vector<node> a;
vector<int> v;
for(int i = 1;i<=n;i++){
int l,r;
cin >>l >> r;
a.push_back({l,r,r-l});
v.push_back(l);
v.push_back(r);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int sz = v.size();
sort(a.begin(),a.end());
build(1,1,2*n);
for(int i = 0;i < n;i++){
a[i].l = lower_bound(v.begin(),v.end(),a[i].l) - v.begin() + 1;
a[i].r = lower_bound(v.begin(),v.end(),a[i].r) - v.begin() + 1;
}
int j = 0;
int ans = 0x3f3f3f3f;
for(int i = 0;i < n;i++){
int l = a[i].l,r = a[i].r;
update(1,l,r,1);
while(j <= i && tr[1].ma == m){
update(1,a[j].l,a[j].r,-1);
ans=min(ans,a[i].len - a[j].len);
j++;
}
}
if(ans==0x3f3f3f3f){
cout << -1 <<endl;
return;
}
cout << ans << endl;
}
线段树+多个标记维护
例题:
1.洛谷P2572 序列操作
链接:
[P2572 SCOI2010] 序列操作 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
维护2个懒标记,和多个普通标记,不只是要加入1的连续,还要加入0的连续,方便反转后的更改
考虑更新lazy,优先级肯定是覆盖操作大,然后才是反转
代码:
#define lc u<<1
#define rc u<<1|1
int a[N];
struct tree{
int l,r;
int s0,l0,r0,m0; //0的个数,左最长,右最长,总最长
int s1,l1,r1,m1; //1的个数,左最长,右最长,总最长
int len;
int rev,tag; //rev 0/1是否取反, tag -1无标记/ 0全部为0 / 1全部为1
}tr[N<<2];
void push_up(tree& t,tree p1,tree p2){
t.s0 = p1.s0 + p2.s0;
t.l0 = p1.s1 ? p1.l0 : p1.s0 + p2.l0;
t.r0 = p2.s1 ? p2.r0 : p2.s0 + p1.r0;
t.m0 = max(p1.r0 + p2.l0,max(p1.m0,p2.m0));
t.s1 = p1.s1 + p2.s1;
t.l1 = p1.s0 ? p1.l1 : p1.s1 + p2.l1;
t.r1 = p2.s0 ? p2.r1 : p2.s1 + p1.r1;
t.m1 = max(p1.r1 + p2.l1,max(p1.m1,p2.m1));
}
void calc(int u,int op){
tree& t = tr[u];
if(op==0){
t.s0 = t.l0 = t.r0 = t.m0 = t.len;
t.s1 = t.l1 = t.r1 = t.m1 = 0;
t.tag=0;
t.rev=0;
}
if(op==1){
t.s0 = t.l0 = t.r0 = t.m0 = 0;
t.s1 = t.l1 = t.r1 = t.m1 = t.len;
t.tag=1;
t.rev=0;
}
if(op==2){
swap(t.s0,t.s1);
swap(t.l0,t.l1);
swap(t.r0,t.r1);
swap(t.m0,t.m1);
t.rev^=1;
}
}
void push_down(int u){
tree& t = tr[u];
if(t.tag==0) calc(lc,0),calc(rc,0);
if(t.tag==1) calc(lc,1),calc(rc,1);
if(t.rev) calc(lc,2),calc(rc,2);
t.tag = -1; t.rev = 0;
}
void build(int u,int l,int r){
int t = a[l];
//如果是t=0 t^1 = 1; 0 的个数 正好是1,1的个数正好是0,反之也合理
tr[u] = {l,r,t^1,t^1,t^1,t^1,t,t,t,t,r-l+1,0,-1};
if(l==r) return;
int mid = l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(tr[u],tr[lc],tr[rc]);
}
void update(int u,int l,int r,int op){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
calc(u,op);
return;
}
push_down(u);
update(lc,l,r,op);
update(rc,l,r,op);
push_up(tr[u],tr[lc],tr[rc]);
}
tree qy(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return { };
if(tr[u].l >= l && tr[u].r <= r){
return tr[u];
}
push_down(u);
tree ne;
push_up(ne,qy(lc,l,r),qy(rc,l,r));
return ne;
}
void solve(){
int n,m;
cin >> n >> m;
for(int i = 1;i<=n;i++) cin >>a[i];
build(1,1,n);
for(int i = 1;i<=m;i++){
int op,l,r;
cin >> op>>l>>r;
++l,++r;
if(op<3){
update(1,l,r,op);
}else if(op==3){
tree ne = qy(1,l,r);
printf("%d\n",ne.s1);
}else if(op==4){
tree ne = qy(1,l,r);
printf("%d\n",ne.m1);
}
}
}
线段树+二分
例题:
1.洛谷P4344 脑洞治疗仪
链接:
[P4344 SHOI2015] 脑洞治疗仪 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
我们维护最长连续0长度,维护1的个数,然后对于前面要填充的区域,我们二分出一个最小合法区域\([l,x](x为我们二分的右边界)\)在最后quary求长度合并时注意代码细节,有注释;
代码:
#define lc u<<1
#define rc u<<1|1
int n,m;
struct tree{
int l,r,len,s1,l1,r1,m1,tag;
}tr[N<<2];
void push_up(tree &u,tree l,tree r){
u.s1 = l.s1+r.s1;
u.l1 = l.s1 ? l.l1 :l.len+r.l1 ;
u.r1 = r.s1 ? r.r1 : l.r1+r.len ;
u.m1 = max(max(l.m1,r.m1),l.r1+r.l1);
}
void build(int u,int l,int r){
tr[u] = {l,r,r-l+1,1,0,0,0,-1};
if(l==r) return;
int mid = l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(tr[u],tr[lc],tr[rc]);
}
void calc(int u,int op){
tree& t = tr[u];
if(op==1){
t.s1 = t.len;
t.l1 = t.r1 = t.m1 = 0;
t.tag = 1;
}else{
t.s1 = 0;
t.l1 = t.r1 = t.m1 = t.len;
t.tag = 0;
}
}
void push_down(int u){
if(tr[u].tag == 1) calc(lc,1),calc(rc,1);
if(tr[u].tag == 0) calc(lc,0),calc(rc,0);
tr[u].tag = -1;
}
//只有两种操作,一种置0,一直置1
void update(int u,int l,int r,int op){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
calc(u,op);
return;
}
push_down(u);
update(lc,l,r,op);
update(rc,l,r,op);
push_up(tr[u],tr[lc],tr[rc]);
}
int q1(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].s1;
}
push_down(u);
return q1(lc,l,r)+q1(rc,l,r);
}
int q0(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u].len - tr[u].s1;
}
push_down(u);
return q0(lc,l,r)+q0(rc,l,r);
}
void work(int l0,int r0,int l1,int r1){
int x = q1(1,l0,r0);
update(1,l0,r0,0);
if(x==0) return;
int l = l1,r = r1,ans = -1;
while(l<=r){
int mid = l+r>>1;
if(q0(1,l1,mid) <= x){
l = mid + 1;
ans = mid;
}else{
r = mid - 1;
}
}
if(ans==-1) return;
update(1,l1,ans,1);
}
tree quary(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return { } ;
if(tr[u].l >= l && tr[u].r <= r){
return tr[u];
}
push_down(u);
if(l > tr[lc].r) return quary(rc,l,r); //在右半部分
if(r < tr[rc].l) return quary(lc,l,r); //在左半部分
tree t;
push_up(t,quary(lc,l,r),quary(rc,l,r));//两个部分各占一点
return t;
}
void solve(){
cin >> n >> m;
build(1,1,n);
while(m--){
int op,l,r;
cin >> op >> l >> r;
if(op==0) update(1,l,r,0);
if(op==1){
int l1,r1;
cin>>l1>>r1;
work(l,r,l1,r1);
}
if(op==2){
cout << quary(1,l,r).m1 << endl;
}
}
}
2.洛谷P2824 排序
链接:
[P2824 HEOI2016/TJOI2016] 排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
思路:
因为是排列,我们想到二分答案,对于一个假定答案x设置>=x的数等于1,小于等于x的数为0,那么构造线段树,可以极快的解决排序,问题然后每次check出来题目要求的idx位置是1那么就左指针右移,为什么?因为x能满足,那么1~x-1都能满足,所以我们区间要去 x+1~r中试图寻找答案
代码:
#define lc u<<1
#define rc u<<1|1
int n,m;
struct qs{
int op,l,r;
}q[N];
//我们二分一个数字,看操作完是否idx这个位置=1;
int a[N];
struct tree{
int l,r,su,len,tag;
}tr[N<<2];
void push_up(int u){
tr[u].su = tr[lc].su + tr[rc].su;
}
void build(int u,int l,int r,int x){
tr[u] = {l,r,(a[l]>=x),r-l+1,-1};
if(l==r)return;
int mid = (l + r) >>1;
build(lc,l,mid,x);
build(rc,mid+1,r,x);
push_up(u);
}
void calc(int u,int op){
if(op==0){
tr[u].su = 0;
}else{
tr[u].su = tr[u].len;
}
tr[u].tag = op;
}
void push_down(int u){
if(tr[u].tag==0) calc(lc,0),calc(rc,0);
if(tr[u].tag==1) calc(lc,1),calc(rc,1);
tr[u].tag = -1;
}
void update(int u,int l,int r,int op){
if(tr[u].l > r || tr[u].r < l) return;
if(tr[u].l >= l && tr[u].r <= r){
calc(u,op);
return;
}
push_down(u);
update(lc,l,r,op);
update(rc,l,r,op);
push_up(u);
}
int q1(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].su;
}
push_down(u);
return q1(lc,l,r) + q1(rc,l,r);
}
int idx;
bool check(int x){
build(1,1,n,x);
for(int i = 1;i <= m;i++){
int op = q[i].op,l = q[i].l,r = q[i].r;
if(op==1){
int cnt = r - l + 1;
int su = q1(1,l,r);
update(1,l,l + su - 1,1);
update(1,l + su,r,0);
}else{
int cnt = r - l + 1;
int su = q1(1,l,r);
update(1,l,r - su,0);
update(1,r - su + 1,r,1);
}
}
return q1(1,idx,idx)==1;
}
void work(){
int l = 1,r = n,ans = -1;
while(l<=r){
int mid = l + r >> 1;
if(check(mid)){
l = mid + 1;
ans = mid;
}else{
r = mid - 1;
}
}
cout << ans << endl;
}
void solve(){
cin >> n >> m;
for(int i =1;i<=n;i++) cin >> a[i];
for(int i = 1;i<=m;i++){
cin >> q[i].op >> q[i].l >> q[i].r;
}
cin >> idx;
work();
}
线段树+数学
例题:
1.洛谷P5142 方差
链接:
P5142 区间方差 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P4344)
思路:
题意:要求一个区间的方差\(\frac{1}{n}\sum_{i=1}^n(a_i - a)^2\) 其中a为区间平均值\(a = \frac{1}{n}\sum_{i=1}^{n}a_i\)
我们将公式化简 为了方便观看,我们将区间平均值设置为\(b\)
\(d = \frac{1}{n}\sum_{i = 1}^n(a_i - b)^2\)
\(=\frac{1}{n}\sum_{i = 1}^n(a_i^2 - 2a_ib + b^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - \sum_{i = 1}^n2a_ib +\sum_{i = 1}^n b^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - 2b\sum_{i = 1}^na_i +n b^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - 2bnb +nb^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - 2nb^2 +nb^2)\)
\(=\frac{1}{n}(\sum_{i = 1}^na_i^2 - nb^2)\)
\(=\frac{1}{n}\sum_{i = 1}^na_i^2 - b^2\)
线段树维护区间和和区间平方和即可
代码:
#define lc u<<1
#define rc u<<1|1
const int N = 200005;
const int MOD = 1e9+7;
int n,m;
int b[N];
struct tree{
int l,r,s1,s2;
}tr[N<<2];
void push_up(int u){
tr[u].s1 = (tr[lc].s1 + tr[rc].s1)%MOD;
tr[u].s2 = (tr[lc].s2 + tr[rc].s2)%MOD;
}
void build(int u,int l,int r){
tr[u] = {l,r,b[l],b[l]*b[l]%MOD};
if(l==r) return;
int mid = l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(u);
}
void update(int u,int x,int v){
if(tr[u].l > x || tr[u].r < x) return;
if(tr[u].l==x&&tr[u].r==x){
tr[u].s1 = v;
tr[u].s2 = (v*v)%MOD;
return;
}
update(lc,x,v);
update(rc,x,v);
push_up(u);
}
int q1(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].s1;
}
return (q1(lc,l,r) + q1(rc,l,r))%MOD;
}
int q2(int u,int l,int r){
if(tr[u].l > r || tr[u].r < l) return 0;
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u].s2;
}
return (q2(lc,l,r) + q2(rc,l,r))%MOD;
}
int ksm(int x,int n){
int res = 1;
while(n){
if(n&1) res = res * x % MOD;
x = x*x%MOD;
n>>=1;
}
return res;
}
void solve(){
cin >> n >> m;
for(int i = 1;i<=n;i++) cin >> b[i];
build(1,1,n);
while(m--){
int op,l,r;
cin >> op >> l >> r;
if(op==1){
update(1,l,r);
}else{
int s1 = q1(1,l,r);
int s2 = q2(1,l,r);
int len = r-l+1;
int iv = ksm(len,MOD-2)%MOD;
s2 = s2*iv%MOD;
s1 = s1*iv%MOD;
s1 = (s1*s1)%MOD;
int res = ((s2 - s1)%MOD + MOD)%MOD;
cout << res <<endl;
}
}
}