线段树

作业介绍

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n,m,a[N],tree[N*4];
void pushup(int rt) {
    //根据左右儿子求父亲
    tree[rt] = tree[rt*2]+tree[rt*2+1];
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update(int l,int r,int rt,int p,int c) {
    if (l==r) {
        tree[rt]+=c;
        return;
    }
    int mid = (l+r)/2;
    if (p<=mid)update(l,mid,rt*2,p,c);
    else update(mid+1,r,rt*2+1,p,c);
    pushup(rt);
}
int query(int l,int r,int rt,int L,int R) {
    //L--l--r--R
    if (L<=l && r<=R) {
        return tree[rt];
    }
    int mid = (l+r)/2,res=0;
    if (L<=mid)res+=query(l,mid,rt*2,L,R);
    if (R>mid)res+=query(mid+1,r,rt*2+1,L,R);
    return res;
}
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,n,1);
    while (m--) {
        int op,x,y;
        cin>>op;
        if (op==1) {
            cin>>x>>y;
            update(1,n,1,x,y);
        }
        else {
            cin>>x>>y;
            cout<<query(1,n,1,x,y)<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,m,tree[N<<2],tag[N<<2],a[N];
void pushup(int rt) {
    tree[rt] = tree[rt<<1] + tree[rt<<1|1];
}
void pushdown(int l,int r,int rt) {
    if (tag[rt]) {
        tag[rt<<1]+=tag[rt];
        tag[rt<<1|1]+=tag[rt];
        int mid = (l+r)>>1;
        tree[rt<<1]+=tag[rt]*(mid-l+1);
        tree[rt<<1|1]+=tag[rt]*(r-mid);
        tag[rt] = 0;
    }
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c) {
    //L--l--r--R
    if (L<=l && r<=R) {
        tag[rt]+=c;
        tree[rt]+=c*(r-l+1);
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)>>1;
    if (L<=mid)update(l,mid,rt<<1,L,R,c);
    if (R>mid)update(mid+1,r,rt<<1|1,L,R,c);
    pushup(rt);
}
int query(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt];
    }
    pushdown(l,r,rt);
    int mid = (l+r)>>1,res=0;
    if (L<=mid)res+=query(l,mid,rt<<1,L,R);
    if (R>mid)res+=query(mid+1,r,rt<<1|1,L,R);
    return res;
}
signed main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,n,1);
    while (m--) {
        int op,x,y,z;
        cin>>op>>x>>y;
        if (op==1) {
            cin>>z;
            update(1,n,1,x,y,z);
        }
        else {
            cout<<query(1,n,1,x,y)<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int T;
int n,m,tree[N<<2];
void pushup(int rt) {
    tree[rt] = tree[rt<<1]*tree[rt<<1|1];
    tree[rt]%=m;
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = 1;
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int p,int c) {
    if (l==r) {
        tree[rt] = c;
        return;
    }
    int mid = (l+r)>>1;
    if (p<=mid)update(l,mid,rt<<1,p,c);
    else update(mid+1,r,rt<<1|1,p,c);
    pushup(rt);
}
signed main() {
    cin>>T;
    while (T--) {
        cin>>n>>m;
        build(1,n,1);
        for (int i=1;i<=n;i++) {
            int op,x,y;
            cin>>op>>x;
            if (op==1) {
                update(1,n,1,i,x);
                cout<<tree[1]<<endl;
            }
            else {
                update(1,n,1,x,1);
                cout<<tree[1]<<endl;
            }
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,m,c,a[N];
struct node {
    int Max,Min;
}tree[N<<2];
void pushup(int rt) {
    tree[rt].Max = max(tree[rt<<1].Max,tree[rt<<1|1].Max);
    tree[rt].Min = min(tree[rt<<1].Min,tree[rt<<1|1].Min);
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = {a[l],a[l]};
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
int queryMax(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt].Max;
    }
    int mid = (l+r)>>1,res=-1e9;
    if (L<=mid)res = max(res,queryMax(l,mid,rt<<1,L,R));
    if (R>mid)res = max(res,queryMax(mid+1,r,rt<<1|1,L,R));
    return res;
}
int queryMin(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt].Min;
    }
    int res = 1e9,mid=(l+r)>>1;
    if (L<=mid)res = min(res,queryMin(l,mid,rt<<1,L,R));
    if (R>mid)res = min(res,queryMin(mid+1,r,rt<<1|1,L,R));
    return res;
}
int main() {
    cin>>n>>m>>c;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,n,1);
    int flag = 0;
    for (int i=1;i+m-1<=n;i++) {
        int Max = queryMax(1,n,1,i,i+m-1);
        int Min = queryMin(1,n,1,i,i+m-1);
        if (Max-Min<=c) {
            flag++;
            cout<<i<<endl;
        }
    }
    if (!flag) {
        cout<<"None"<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
struct node {
    int val,flag,tag,add;//val值，flag是否被修改，tag修改后的值，add增加的值
}tree[N<<2];
int n,m,a[N];
void pushup(int rt) {
    tree[rt].val = max(tree[rt<<1].val,tree[rt<<1|1].val);
}
void pushdown(int rt) {
    if (tree[rt].flag) {
        tree[rt<<1].flag=tree[rt].flag;
        tree[rt<<1|1].flag=tree[rt].flag;
        tree[rt<<1].tag=tree[rt].tag;
        tree[rt<<1|1].tag=tree[rt].tag;
        tree[rt<<1].add=tree[rt].add;
        tree[rt<<1|1].add=tree[rt].add;
        tree[rt<<1].val=tree[rt].tag+tree[rt].add;
        tree[rt<<1|1].val=tree[rt].tag+tree[rt].add;
        tree[rt].flag = 0;
        tree[rt].tag = 0;
        tree[rt].add = 0;
    }
    else if (tree[rt].add) {
        tree[rt<<1].add+=tree[rt].add;
        tree[rt<<1|1].add+=tree[rt].add;
        tree[rt<<1].val+=tree[rt].add;
        tree[rt<<1|1].val+=tree[rt].add;
        tree[rt].add = 0;
    }
}
void build(int l,int r,int rt) {
    tree[rt].flag = 0;
    tree[rt].add = 0;
    tree[rt].tag = 0;
    if (l==r) {
        tree[rt].val = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void change(int l,int r,int rt,int L,int R,int c) {
    if (L<=l && r<=R) {
        tree[rt].flag = 1;
        tree[rt].tag = c;
        tree[rt].add = 0;
        tree[rt].val = c;
        return;
    }
    pushdown(rt);
    int mid = (l+r)>>1;
    if (L<=mid)change(l,mid,rt<<1,L,R,c);
    if (R>mid)change(mid+1,r,rt<<1|1,L,R,c);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c) {
    if (L<=l && r<=R) {
        tree[rt].add+=c;
        tree[rt].val+=c;
        return;
    }
    pushdown(rt);
    int mid = (l+r)>>1;
    if (L<=mid)update(l,mid,rt<<1,L,R,c);
    if (R>mid)update(mid+1,r,rt<<1|1,L,R,c);
    pushup(rt);
}
int query(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt].val;
    }
    int mid = (l+r)>>1,res=-1e18;
    pushdown(rt);
    if (L<=mid)res = max(res,query(l,mid,rt<<1,L,R));
    if (R>mid)res = max(res,query(mid+1,r,rt<<1|1,L,R));
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,n,1);
    while (m--) {
        int op,x,y,z;
        cin>>op>>x>>y;
        if (op==1) {
            cin>>z;
            change(1,n,1,x,y,z);
        }
        else if (op==2) {
            cin>>z;
            update(1,n,1,x,y,z);
        }
        else {
            cout<<query(1,n,1,x,y)<<endl;
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,T,m;
int tag[N<<2],tree[N<<2];
void pushup(int rt) {
    tree[rt] = tree[rt<<1]|tree[rt<<1|1];
}
void pushdown(int rt) {
    if (tag[rt]) {
        tag[rt<<1]=tag[rt];
        tag[rt<<1|1] = tag[rt];
        tree[rt<<1] = (1<<(tag[rt]-1));
        tree[rt<<1|1] = (1<<(tag[rt]-1));
        tag[rt] = 0;
    }
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = 1;
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,int c) {
    if (L<=l && r<=R) {
        tag[rt] = c;
        tree[rt] = (1<<(c-1));
        return;
    }
    int mid = (l+r)>>1;
    pushdown(rt);
    if (L<=mid)update(l,mid,rt<<1,L,R,c);
    if (R>mid)update(mid+1,r,rt<<1|1,L,R,c);
    pushup(rt);
}
int query(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt];
    }
    pushdown(rt);
    int mid = (l+r)>>1,res=0;
    if (L<=mid)
        res|=query(l,mid,rt<<1,L,R);
    if (R>mid)
        res|=query(mid+1,r,rt<<1|1,L,R);
    return res;
}
int Get(int x) {
    int res = 0;
    while (x) {
        if (x%2==1)res++;
        x/=2;
    }
    return res;
}
int main() {
    cin>>n>>T>>m;
    build(1,n,1);
    while (m--) {
        char op;
        int x,y,z;
        cin>>op>>x>>y;
        if (x>y)swap(x,y);
        if (op=='C') {
            cin>>z;
            update(1,n,1,x,y,z);
        }
        else {
            cout<<Get(query(1,n,1,x,y))<<endl;
        }
    }
    return 0;
}

/*
 *
 * pushup
 * sum和
 * Mx最大子段和
 * Lmax从最左边开始的最大子段和
 * Rmax以右断点结尾的最大子段和
 * rt.Lmax = max(rt<<1.Lmax,rt<<1.sum+rt<<1|1.Lmax)
 * rt.Rmax = max(rt<<1|1.Rmax,rt<<1|1.sum+rt<<1.Rmax)
 *
 * rt.Mx = max(rt<<1.Mx,rt<<1|1.Mx,rt<<1.Rmax+rt<<1|1.Lmax)
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
struct node {
    int sum,Mx,Lmx,Rmx;
    friend node operator + (node a,node b) {
        node c;
        c.sum = a.sum+b.sum;
        c.Lmx = max(a.Lmx,a.sum+b.Lmx);
        c.Rmx = max(b.Rmx,b.sum+a.Rmx);
        c.Mx = max(max(a.Mx,b.Mx),a.Rmx+b.Lmx);
        c.Mx = max(c.Mx,max(c.Lmx,c.Rmx));
        return c;
    }
}tree[N<<2];
int n,m,a[N];
void pushup(int rt) {
    tree[rt] = tree[rt<<1]+tree[rt<<1|1];
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = {a[l],a[l],a[l],a[l]};
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int p,int c) {
    if (l==r) {
        tree[rt] = {c,c,c,c};
        return;
    }
    int mid = (l+r)>>1;
    if (p<=mid)update(l,mid,rt<<1,p,c);
    else update(mid+1,r,rt<<1|1,p,c);
    pushup(rt);
}
node query(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt];
    }
    int mid = (l+r)>>1;
    if (L<=mid && R>mid)return query(l,mid,rt<<1,L,R)+query(mid+1,r,rt<<1|1,L,R);
    else if (L<=mid)return query(l,mid,rt<<1,L,R);
    else if (R>mid)return query(mid+1,r,rt<<1|1,L,R);
}
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,n,1);
    while (m--) {
        int op,x,y,z;
        cin>>op>>x>>y;
        if (op==1) {
            if (x>y)swap(x,y);
            cout<<query(1,n,1,x,y).Mx<<endl;
        }
        else {
            update(1,n,1,x,y);
        }
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,m;
double a[N],tag[N<<2];
struct node {
    double sum,sum2;
}tree[N<<2];
void pushup(int rt) {
    tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
    tree[rt].sum2 = tree[rt<<1].sum2+tree[rt<<1|1].sum2;
}
void pushdown(int l,int r,int rt) {
    if (tag[rt]!=0) {
        tag[rt<<1]+=tag[rt];
        tag[rt<<1|1]+=tag[rt];
        int mid = (l+r)>>1;
        tree[rt<<1].sum2+=2*tag[rt]*tree[rt<<1].sum+tag[rt]*tag[rt]*(mid-l+1);
        tree[rt<<1|1].sum2+=2*tag[rt]*tree[rt<<1|1].sum+tag[rt]*tag[rt]*(r-mid);
        tree[rt<<1].sum+=tag[rt]*(mid-l+1);
        tree[rt<<1|1].sum+=tag[rt]*(r-mid);
        tag[rt] = 0;
    }
}
void build(int l,int r,int rt) {
    if (l==r) {
        tree[rt] = {a[l],a[l]*a[l]};
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int l,int r,int rt,int L,int R,double c) {
    if (L<=l && r<=R) {
        tag[rt]+=c;
        tree[rt].sum2+=2*c*tree[rt].sum+c*c*(r-l+1);
        tree[rt].sum+=c*(r-l+1);
        return;
    }
    pushdown(l,r,rt);
    int mid = (l+r)>>1;
    if (L<=mid)update(l,mid,rt<<1,L,R,c);
    if (R>mid)update(mid+1,r,rt<<1|1,L,R,c);
    pushup(rt);
}
double query1(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R)return tree[rt].sum;
    pushdown(l,r,rt);
    double res = 0;
    int mid = (l+r)>>1;
    if (L<=mid)res+=query1(l,mid,rt<<1,L,R);
    if (R>mid)res+=query1(mid+1,r,rt<<1|1,L,R);
    return res;
}
double query2(int l,int r,int rt,int L,int R) {
    if (L<=l && r<=R) {
        return tree[rt].sum2;
    }
    double res = 0;
    pushdown(l,r,rt);
    int mid = (l+r)>>1;
    if (L<=mid)res+=query2(l,mid,rt<<1,L,R);
    if (R>mid)res+=query2(mid+1,r,rt<<1|1,L,R);
    return res;
}
int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    build(1,n,1);
    while (m--) {
        int op,x,y;
        double z;
        cin>>op>>x>>y;
        if (op==1) {
            cin>>z;
            update(1,n,1,x,y,z);
        }
        else if (op==2) {
            double sum = query1(1,n,1,x,y);
            cout<<fixed<<setprecision(4)<<sum/(y-x+1)<<endl;
        }
        else {
            double sum=query1(1,n,1,x,y);
            double sum2=query2(1,n,1,x,y);
            double res = (sum2-sum*sum/double(y-x+1))/double(y-x+1);
            cout<<fixed<<setprecision(4)<<res<<endl;


            //s2 =
        }
    }
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
long long a[N], tree[N << 2];

void pushup (int rt) {
	tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}

void build (int l, int r, int rt) {
	if (l == r) {
		tree[rt] = a[l];
		return ;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update (int l, int r, int rt, int L, int R) {
	if (tree[rt] == r - l + 1)
		return ;
	if (l == r) {
		tree[rt] = sqrt(tree[rt]);
		return ;
	}
	int mid = l + r >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R);
	pushup(rt);
}

long long query(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R)
		return tree[rt];
	int mid = l + r >> 1;
	long long res = 0;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

int main (void) {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	build(1, n, 1);
	cin >> m;
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (x > y)
			swap(x, y);
		if (op == 0)
			update(1, n, 1, x, y);
		else
			cout << query(1, n, 1, x, y) << '\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, a[N], b[N];
int tree[N << 2];

void pushup(int rt) {
	tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void update(int l, int r, int rt, int p, int c) {
	if (l == r) {
		tree[rt] += c;
		return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid)
		update(l, mid, rt << 1, p, c);
	else
		update(mid + 1, r, rt << 1 | 1, p, c);
	pushup(rt);
}

int query(int l, int r, int rt, int c) {
	if (l == r) {
		return l;
	}
	int mid = (l + r) >> 1;
	if (tree[rt << 1] >= c)
		return query(l, mid, rt << 1, c);
	else
		return query(mid + 1, r, rt << 1 | 1, c);
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		if (tree[1] < b[i]) {
			cout << 0 << " ";
			continue;
		}
		int tmp = query(1, n, 1, b[i]);
		cout << tmp << " ";
		update(1, n, 1, tmp, -b[i]);
	}
	return 0;
}

题目

题目
P3374   【模板】树状数组 1
P3372   【模板】线段树 1
P4588   [TJOI2018] 数学计算
P4392   [BalticOI 2007] Sound 静音问题
P1816   忠诚
P4513   小白逛公园
P2357   守墓人
P2068   统计和
P4939   Agent2
P3373   【模板】线段树 2
P2023   [AHOI2009] 维护序列
P1253   扶苏的问题
P1558   色板游戏
P1471   方差
P1607   [USACO09FEB] Fair Shuttle G
P4145   上帝造题的七分钟 2 / 花神游历各国
P1438   无聊的数列
P2846   [USACO08NOV] Light Switching G
P3740   [HAOI2014] 贴海报
P3797   妖梦斩木棒
P4137   Rmq Problem / mex
P1503   鬼子进村
P2471   [SCOI2007] 降雨量
P2574   XOR的艺术
P5490   【模板】扫描线 & 矩形面积并
P6327   区间加区间 sin 和
P10463   Interval GCD
P2221   [HAOI2012] 高速公路
P1937   [USACO10MAR] Barn Allocation G
CSES1143   酒店查询
CSES1749   列表删除
CSES2166   前缀和查询
CSES2206   披萨店查询
状态
已结束
题目
33
开始时间
2026-7-27 0:00
截止时间
2026-8-4 23:59
可延期
24 小时
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 蜀ICP备202200548-2号
  3. Worker 0, 21ms
  4. Powered by Hydro v5.0.1 Community