比赛 Asm.Def战记之圣地亚哥“杯2015 评测结果 AAAAAAAWWW
题目名称 Asm.Def的命令 最终得分 70
用户昵称 氢氦 运行时间 0.635 s
代码语言 C++ 内存使用 38.84 MiB
提交时间 2019-10-23 17:56:49
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long

const int maxn = 1e5 + 5;
int n, q, a[maxn];

template<class T>
inline T read(T &x) {
	x = 0; int w = 1, ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - 48;
	return x *= w;
}

struct Segment_Tree {
	int L[maxn << 2], R[maxn << 2], sum[maxn << 2], tag[maxn << 2];

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

		void pushdown(int rt)
		{
		    long long v=tag[rt];tag[rt]=0;
		    int ls=rt<<1,rs=rt<<1|1;
		    sum[ls]+=v * (R[ls]-L[ls]+1);
		    sum[rs]+=v * (R[rs]-L[rs]+1);
		    tag[ls]+=v,tag[rs]+=v;
		}

		void modify(int rt,int l,int r,int x)
		{
		    if(L[rt]==l&&R[rt]==r){
		        sum[rt]+=(r-l+1) * (long long)x;
		        tag[rt]+=x;return ;
		    }
		    int mid=(L[rt]+R[rt])>>1;pushdown(rt);
		    if(r<=mid)
		        modify(rt<<1,l,r,x);
		    if(l>mid)
		        modify(rt<<1|1,l,r,x);
		    if(l<=mid&&r>mid){
		        modify(rt<<1,l,mid,x);
		        modify(rt<<1|1,mid+1,r,x);
		    }
		    sum[rt]=sum[rt<<1]+sum[rt<<1|1];		
		}

		long long query(int rt,int l,int r)
		{
		    if(L[rt]==l&&R[rt]==r)return sum[rt];
		    int mid=(L[rt]+R[rt])>>1;pushdown(rt);
		    if(r<=mid)
		        return query(rt<<1,l,r);
		    if(l>mid)
		        return query(rt<<1|1,l,r);
		    return query(rt<<1,l,mid)+query(rt<<1|1,mid+1,r);		
		}
}X, Y;

signed main() {
	freopen("asm_command.in", "r", stdin);
	freopen("asm_command.out", "w", stdout);
	read(n), read(q);
	memset(a, 0, sizeof(a));
	X.build(1, 1, n);
	for (int i = 1; i <= n; i++) a[i] = i;
	Y.build(1, 1, n);
	int opt, l, r, dx, dy;
	for (int i = 1; i <= q; i++) {
		read(opt);
		if (opt == 1) {
			read(l), read(r), read(dx), read(dy);
			X.modify(1, l, r, dx);
			Y.modify(1, l, r, dy);
		}
		else if (opt == 0) {
			read(l);
			int xx = X.query(1, l, l), yy = Y.query(1, l, l);
			std::cout << xx << ".0" << ' ' << yy << ".0" << '\n';
		}
		else {
			read(l), read(r), read(dx);
			continue;
		}
	}
	return 0;
}

/*
5 6
1 1 3 -2 0
0 2
2 1 5 90
0 1
0 2
0 5
复杂度O(玄学)
*/