传送门
题面：
Naive Operations
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 502768/502768 K (Java/Others)
Total Submission(s): 650 Accepted Submission(s): 239
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
题意：
给你一个数组a[i]和b[i]，其中a[i]最开始为0，b[i]为n的任意排列。有两种操作，第一种在区间[l,r]中将a[i]加1。第二种统计区间[l,r]的 ai/bi（下取整）的和。
分析：算法肯定是线段树，我们观察a[i]/b[i]（下取整）什么时候才能+1，a[i]在区间更新的时候+1到b[i],加到n*b[i]就有n个1，这时候我们可以用sum++记录加1的个数，我们可以维护a的最大值maxa和b的最小值minb。
在区间更新的时候，如果maxa<minb,没有必要向下更新
f否则一直更新到所需要的点，到达后，sum++，minnb+=b[l](为下一次+1更新值）
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
using namespace std;#define lson i<<1
#define rson i<<1|1
#define LS l,mid,lson
#define RS mid+1,r,rson
#define ll long long
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define EXP 1e-8
#define lowbit(x) (x&-x)ll b[N];
ll ans_sum,ans_max,ans_min;
struct node
{int l,r;ll sum,maxa,minb;ll add;
} a[N<<2];void pushdown(int i)//标记下传
{if(a[i].add!=0){a[lson].add+=a[i].add;///给左子节点打上延迟标记a[rson].add+=a[i].add;///给右子节点打上延迟标记a[lson].maxa+=a[i].add;a[rson].maxa+=a[i].add;a[i].add = 0; ///清除标记}}void pushup(int i)
{a[i].sum=a[lson].sum+a[rson].sum;a[i].maxa=max(a[lson].maxa,a[rson].maxa);a[i].minb=min(a[lson].minb,a[rson].minb);
}
//建立线段树
void build(int l,int r,int i)
{a[i].l = l;a[i].r = r;a[i].add = 0;if(l == r) {a[i].sum = 0;a[i].maxa = 0;a[i].minb= b[l];return;}int mid = (l+r)>>1;build(LS);build(RS);pushup(i);
}
//a[l,r]+=val
void add_data(int l,int r,int i,ll val)
{if(a[i].l>=l&&a[i].r<=r){a[i].maxa+=val;if(a[i].maxa<a[i].minb){a[i].add+=val;return;}if(a[i].l==a[i].r&&a[i].maxa>=a[i].minb){a[i].sum++;a[i].minb+=b[a[i].l];return;}}pushdown(i);//标记下传int mid = (a[i].l+a[i].r)>>1;if(l<=mid) add_data(l,r,lson,val);if(r>mid) add_data(l,r,rson,val);pushup(i);
}void query(int l,int r,int i)
{//cout<<l<<" "<<r<<" "<<i<<endl;if(l <= a[i].l && a[i].r <= r){ans_sum += a[i].sum;return ;}pushdown(i);int mid = (a[i].l+a[i].r)>>1;if(l<=mid) query(l,r,lson);if(r>mid) query(l,r,rson);pushup(i);
}int main()
{int n,m;while(scanf("%d%d",&n,&m)!=-1){for (int i=1;i<=n;i++){scanf("%lld",&b[i]);}build(1,n,1); char ch[2];while(m--){int l, r;scanf("%s", ch);if(ch[0] == 'a'){int x,y;ll v;scanf("%d %d", &x,&y);add_data(x,y,1,1);}else{scanf("%d %d", &l,&r);//cout<<l<<" "<<r<<endl;ans_sum=0;query(l,r,1);printf("%lld\n",ans_sum);}}}return 0;
}