多校的原题，蒟蒻来补题了，暑假还不会线段树QAQ

题意

给n,m两个数字，表示数组大小和操作次数，给一个数组b和一个初始值全部为0的数组a，每次操作add可以在给定的区间(l,r)内让a[i](l=<i<=r)加一，或者query查询区间区间(l,r)中a[i]/b[i](l=<i<=r)(取整)的和。

思路

很裸的线段树吧，就是操作麻烦了一点，注意70行不能用que[k].maxa -= que[k].minb;，这样会导致每次都更新到底，和暴力没什么区别，（手动模拟可以验证）。

代码

#include <iostream>
#include <algorithm>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1
using namespace std;
ll a[200005], val;
int ql, qr;
struct node
{
	int l;
	int r;
	ll sum;
	ll mark;//懒惰标记 maxa增加的次数
	ll maxa;
	ll minb;//minb
}que[200005 * 4];
void pup(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
	que[k].minb = min(que[k << 1].minb, que[k << 1 | 1].minb);
	que[k].maxa = max(que[k << 1].maxa, que[k << 1 | 1].maxa);
}
void pdown(int k)
{
	if (que[k].mark)
	{
		que[k << 1].mark += que[k].mark;
		que[k << 1 | 1].mark += que[k].mark;
		que[k << 1].maxa += que[k].mark;
		que[k << 1 | 1].maxa += que[k].mark;
		que[k].mark = 0;
	}
}
void build(int left, int right, int k)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = 0;
	if (left == right)
	{
		que[k].maxa = 0;
		que[k].minb = a[left];
		que[k].sum = 0;
		return;
	}
	imid;
	build(left, mid, k << 1);
	build(mid + 1, right, k << 1 | 1);
	pup(k);
}
void update(int left, int right, int k)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].maxa++;
		if (que[k].maxa < que[k].minb)
		{
			que[k].mark++;
			return;
		}
		if (left == right)
		{
			while (que[k].maxa >= que[k].minb)
			{
				que[k].minb += a[que[k].l];
				//que[k].maxa -= que[k].minb;
				//注意这里是把min加上a[i],不能用max减a[i]，
				//虽然值一样但是后者操作相当于让懒惰标记没有了，
				//以为你大区间的max依旧不变，
				//所以每次更新都要跑到底导致超时
				que[k].sum++;
			}
			return;
		}
	}
	pdown(k);
	imid;
	update(lson);
	update(rson);
	pup(k);
}
ll query(int left, int right, int k)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum;
	pdown(k);
	imid;
	return query(lson) + query(rson);
}
int main()
{
	int n, m;
	char s[5];
	while (scanf("%d%d", &n, &m) > 0)
	{
		for (int i = 1; i <= n; i++)
			scanf("%lld", &a[i]);
		build(1, n, 1);
		while (m--)
		{
			scanf("%s%d%d", s, &ql, &qr);
			if (s[0] == 'a')
				update(1, n, 1);
			else
				printf("%lld\n", query(1, n, 1));
		}
	}
}