Naive Operations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 502768/502768 K (Java/Others)
Total Submission(s): 853    Accepted Submission(s): 318

Problem Description

In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for al,al+1...ar
2. query l r: query ∑ri=l⌊ai/bi]

Input

There are multiple test cases, please read till the end of input file.
For each test case, in the first line, two integers n,q, representing the length of a,b and the number of queries.
In the second line, n integers separated by spaces, representing permutation b.
In the following q lines, each line is either in the form 'add l r' or 'query l r', representing an operation.
1≤n,q≤100000, 1≤l≤r≤n, there're no more than 5 test cases.

Output

Output the answer for each 'query', each one line.

Sample Input

5 12

1 5 2 4 3

add 1 4

query 1 4

add 2 5

query 2 5

add 3 5

query 1 5

add 2 4

query 1 4

add 2 5

query 2 5

add 2 2

query 1 5

Sample Output

1

1

2

4

4

6

Source

2018 Multi-University Training Contest 2

题意：

有一个a数组和b数组，大小都为n个，a数组初始每个都为0，b数组的数为1 到 n，现在有两种操作：

1.在a数组的l到r区间都加上1   即区间更新

2.查询区间 l到r 的     ai/bi  的区间和    即区间查询（注意a数组和b数组都是int类型，所以是整除）

一开始输入两个数，为n，m，分别是数组大小和操作次数

然后输入一个字符串和两个整数 判断是哪种操作以及区间大小

题解思路：

一开始做这道题，第一眼就觉得是线段树，立马敲了个版，tle了一发，全程优化时间复杂度， 最后还是没想出不来，真的弱QAQ。

晚上看了杜老师直播恍然大悟！！

看了别人的题解，写了一种方法。

维护一个区间 a 的最大值，b的最小值，用一个lazy来标记区间增加过的次数，当aa<bb就可以不用向下更新了。

当更新到单点并且 aa>bb 时，区间答案sum加一，bb+=b[l] 

其他全部全部都是线段树的模板QAQ~

我真的是太菜了~~~~

附上本弱者的AC代码：

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

struct node {
	int l, r, aa, bb, lazy, sum;//sum为区间和 
}tree[maxn<<2];
int n, m, ll, rr, b[maxn];
char ss[20];

void pushdown(int root){
	if(tree[root].lazy){
		tree[root<<1].lazy += tree[root].lazy;
		tree[root<<1|1].lazy += tree[root].lazy;
		tree[root<<1].aa += tree[root].lazy;
		tree[root<<1|1].aa += tree[root].lazy;
		tree[root].lazy = 0;
	}
}
void pushup(int root){
	tree[root].bb = min(tree[root<<1].bb, tree[root<<1|1].bb);
	tree[root].aa = max(tree[root<<1].aa, tree[root<<1|1].aa);
	tree[root].sum = tree[root<<1].sum + tree[root<<1|1].sum;
}
void buildtree(int l, int r, int root){
	tree[root].lazy = 0;
	tree[root].l = l;
	tree[root].r = r;
	if(l == r){
		tree[root].bb = b[l];
		tree[root].sum = tree[root].aa = 0;
		return;
	}
	int mid = l+r>>1;
	buildtree(l, mid, root<<1);
	buildtree(mid+1, r, root<<1|1);
	pushup(root); 
}
void update(int l, int r, int root){
	if(l <= tree[root].l && tree[root].r <= r){
		tree[root].aa++;
		if(tree[root].aa < tree[root].bb){
			tree[root].lazy++;
			return ;
		}
		if(tree[root].l == tree[root].r && tree[root].aa >= tree[root].bb){
			tree[root].sum++;
			tree[root].bb += b[tree[root].l];
			return;
		}
	}
	pushdown(root);
	int mid= tree[root].l + tree[root].r >> 1;
	if(l <= mid){
		update(l, r, root<<1);
	}
	if(r > mid){
		update(l, r, root<<1|1);
	}
	pushup(root);
}
int query(int l, int r, int root){
	if(l <= tree[root].l && tree[root].r <= r){
		return tree[root].sum;
	}
	pushdown(root);
	int ans = 0, mid = tree[root].l + tree[root].r >> 1;
	if(l <= mid){
		ans += query(l, r, root<<1);
	}if(r > mid){
		ans += query(l, r, root<<1|1);
	}
	return ans;
}
int main() {
	while(~scanf("%d%d", &n, &m)){
		for(int i = 1; i <= n; i++){
			scanf("%d", &b[i]);
		}
		buildtree(1, n, 1);
		for(int i = 0; i < m; i++){
			scanf("%s%d%d", ss, &ll, &rr);
			if(ss[0] == 'a'){
				update(ll, rr, 1);
			}else {
				printf("%d\n", query(ll, rr, 1));
			}
		}	
	}
	return 0;
}

还要继续努力呀！！QAQ