作业详情 - 蒙青创OJ

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

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 sum = 0;
	int mid = (l + r) / 2;
	if (L <= mid)
		sum += query(l, mid, rt * 2, L, R);
	if (R > mid)
		sum += query(mid + 1, r, rt * 2 + 1, L, R);
	return sum;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	while (m--) {
		int op, l, r;
		cin >> op >> l >> r;
		if (op == 1) {
			update(1, n, 1, l, r);
		} else
			cout << query(1, n, 1, l, r) << endl;
	}
	return 0;
}

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

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, Inf = 2e9;
int n, m, a[N];

struct node {
	int Max, tag1, tag2;
	//tag1代表修改，tag2代表增加
} tree[N << 2];

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

void pushdown(int rt) {
	if (tree[rt].tag1 != Inf) {
		tree[rt << 1].tag1 = tree[rt].tag1;
		tree[rt << 1 | 1].tag1 = tree[rt].tag1;
		tree[rt << 1].tag2 = tree[rt].tag2;
		tree[rt << 1 | 1].tag2 = tree[rt].tag2;
		tree[rt << 1].Max = tree[rt].tag1 + tree[rt].tag2;
		tree[rt << 1 | 1].Max = tree[rt].tag1 + tree[rt].tag2;
		tree[rt].tag1 = Inf;
		tree[rt].tag2 = 0;
	} else if (tree[rt].tag2) {
		tree[rt << 1].tag2 += tree[rt].tag2;
		tree[rt << 1 | 1].tag2 += tree[rt].tag2;
		tree[rt << 1].Max += tree[rt].tag2;
		tree[rt << 1 | 1].Max += tree[rt].tag2;
		tree[rt].tag2 = 0;
	}
}

void build(int l, int r, int rt) {
	tree[rt].tag1 = Inf;
	if (l == r) {
		tree[rt].Max = 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].tag1 = c;
		tree[rt].tag2 = 0;
		tree[rt].Max = 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].tag2 += c;
		tree[rt].Max += 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].Max;
	}
	pushdown(rt);
	int mid = (l + r) >> 1, res = -1000000000000000000;
	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, m;
double a[N];

struct node {
	double sum, sum2, tag;
} 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 (tree[rt].tag != 0) {
		tree[rt << 1].tag += tree[rt].tag;
		tree[rt << 1 | 1].tag += tree[rt].tag;
		/*
		sigma(a[i]+c)^2 = sigma(a[i]^2+2*c*a[i]+c^2)
		*/
		int mid = (l + r) >> 1;
		tree[rt << 1].sum2 = tree[rt << 1].sum2 + 2 * tree[rt].tag * tree[rt << 1].sum + tree[rt].tag * tree[rt].tag *
		                     (mid - l + 1);
		tree[rt << 1 | 1].sum2 = tree[rt << 1 | 1].sum2 + 2 * tree[rt].tag * tree[rt << 1 | 1].sum + tree[rt].tag *
		                         tree[rt].tag * (r - mid);

		tree[rt << 1].sum += tree[rt].tag * (mid - l + 1);
		tree[rt << 1 | 1].sum += tree[rt].tag * (r - mid);
		tree[rt].tag = 0;
	}
}

void build(int l, int r, int rt) {
	if (l == r) {
		tree[rt].sum = a[l];
		tree[rt].sum2 = 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) {
		tree[rt].tag += c;
		tree[rt].sum2 = 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 querysum(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt].sum;
	}
	pushdown(l, r, rt);
	double sum = 0;
	int mid = (l + r) >> 1;
	if (L <= mid)
		sum += querysum(l, mid, rt << 1, L, R);
	if (R > mid)
		sum += querysum(mid + 1, r, rt << 1 | 1, L, R);
	return sum;
}

double querysum2(int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R) {
		return tree[rt].sum2;
	}
	pushdown(l, r, rt);
	double sum = 0;
	int mid = (l + r) >> 1;
	if (L <= mid)
		sum += querysum2(l, mid, rt << 1, L, R);
	if (R > mid)
		sum += querysum2(mid + 1, r, rt << 1 | 1, L, R);
	return sum;
}

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;
		double z;
		cin >> op >> x >> y;
		if (op == 1) {
			cin >> z;
			update(1, n, 1, x, y, z);
		} else if (op == 2) {
			double res = querysum(1, n, 1, x, y);
			cout << fixed << setprecision(4) << res / double(y - x + 1) << endl;
		} else {
			double sum = querysum(1, n, 1, x, y);
			double ave = sum / double(y - x + 1);
			double sum2 = querysum2(1, n, 1, x, y);
			double res = sum2 - 2 * sum * ave + (ave * ave) * (y - x + 1);
			res /= double(y - x + 1);
			cout << fixed << setprecision(4) << res << endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e4 + 5;
int tree[N << 2], tag[N << 2];
int n, m, k;

struct node {
	int l, r, x;
} p[N*3];

bool cmp(node a, node b) {
	if (a.r == b.r)
		return a.l > b.l;
	return a.r < b.r;
}

void pushup(int rt) {
	tree[rt] = max(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];
		tree[rt << 1 | 1] += tag[rt];
		tag[rt] = 0;
	}
}

void update(int l, int r, int rt, int L, int R, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		tree[rt] += c;
		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;
	int res = 0;
	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() {
	cin >> m >> n >> k;
	for (int i = 1; i <= m; i++) {
		cin >> p[i].l >> p[i].r >> p[i].x;
	}
	sort(p + 1, p + m + 1, cmp);
	int res = 0;
	for (int i = 1; i <= m; i++) {
		int l = p[i].l, r = p[i].r, c = p[i].x;
		int Max = query(1, n, 1, l, r - 1);
		if (Max + c <= k)
			res += c, update(1, n, 1, l, r - 1, c);
		else {
			res += k - Max;
			update(1, n, 1, l, r - 1, k - Max);
		}
	}
	cout << res << endl;
	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;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,m,p[N];
struct node{
	int v1,v2;//v1 p[i]+a[i]  v2 p[i]-a[i]
}tree[N<<2];
void pushup(int rt)
{
	tree[rt].v1 = min(tree[rt<<1].v1,tree[rt<<1|1].v1);
	tree[rt].v2 = min(tree[rt<<1].v2,tree[rt<<1|1].v2);
}
void build(int l,int r,int rt)
{
	if(l==r){
		tree[rt].v1 = p[l]+l;
		tree[rt].v2 = p[l]-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 x,int c)
{
	if(l==r){
		tree[rt].v1 = c+x;
		tree[rt].v2 = c-x;
		return;
	}
	int mid = (l+r)>>1;
	if(x<=mid)update(l,mid,rt<<1,x,c);
	else update(mid+1,r,rt<<1|1,x,c);
	pushup(rt);
}
int query1(int l,int r,int rt,int L,int R)
{
	if(L<=l && r<=R){
		return tree[rt].v1;
	}
	int mid = (l+r)>>1;
	int res = 2e9;
	if(L<=mid)res = min(res,query1(l,mid,rt<<1,L,R));
	if(R>mid)res = min(res,query1(mid+1,r,rt<<1|1,L,R));
	return res;
}
int query2(int l,int r,int rt,int L,int R)
{
	if(L<=l && r<=R){
		return tree[rt].v2;
	}
	int mid = (l+r)>>1;
	int res = 2e9;
	if(L<=mid)res = min(res,query2(l,mid,rt<<1,L,R));
	if(R>mid)res = min(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>>p[i];
	} 
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int pos,x,y;
		cin>>pos>>x;
		if(pos==1){
			cin>>y;
			int tmp = y-p[x];
			p[x] = y;
			update(1,n,1,x,y);
		}
		else{
			int res = 2e9;
			res = min(res,query1(1,n,1,x,n)-x);
			res = min(res,query2(1,n,1,1,x)+x);
			cout<<res<<endl;
		}
	}
	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-3 0:00
截止时间: 2026-7-10 23:59
可延期: 24 小时

作业介绍

题目

登录