hdu 6315 http://acm.hdu.edu.cn/showproblem.php?pid=6315
题意: 对于一个数列 a, 初始为 0, 每个 a[i] 对应一个 b[i], 只有在这个数字上加了 b[i] 次后, a[i] 才会 + 1.
有 q 次操作, 一种是个区间加 1, 一种是查询 a 的区间和.
思路: 线段树, 一开始没用 lazy,TLE 了, 然后开始想 lazy 的标记, 这棵线段树的特点是, 每个节点维护 : 一个区间某个 a 要增加 1 所需个数的最小值, 一个区间已加上的 mx 的最大值标记, 还有就是区间和 sum. (自己一开始没有想到 mx 标记, 一度想把 lazy 传回去.
(思路差一点就多开节点标记.
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <list>
- #include <cstdlib>
- #include <iterator>
- #include <cmath>
- #include <iomanip>
- #include <bitset>
- #include <cctype>
- #include <stack>
- #pragma comment(linker, "/STACK:102400000,102400000") //c++
- using namespace std;
- #define lson (l , mid , rt <<1)
- #define rson (mid + 1 , r , rt << 1 | 1)
- #define debug(x) cerr << #x << "=" << x << "\n";
- #define pb push_back
- #define pq priority_queue
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<ll ,ll> pll;
- typedef pair<int ,int> pii;
- #define fi first
- #define se second
- #define OKC ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
- #define FT(A,B,C) for(int A=B;A <= C;++A) // 用来压行
- #define REP(i , j , k) for(int i = j ; i <k ; ++i)
- const ll mos = 0x7FFFFFFF; //2147483647
- const ll nmos = 0x80000000; //-2147483648
- const int inf = 0x3f3f3f3f;
- template<typename T>
- inline T read(T&x){
- x=0;int f=0;char ch=getchar();
- while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
- while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
- return x=f?-x:x;
- }
- // #define _DEBUG; //*//
- #ifdef _DEBUG
- freopen("input", "r", stdin);
- // freopen("output.txt", "w", stdout);
- #endif
- /*----------------------show time----------------------*/
- int n,q;
- const int maxn = 100009;
- int a[maxn],b[maxn];
- int sum[maxn*4];
- int lazy[maxn*4];
- int mx[maxn*4];
- int nd[maxn*4];
- void pushup(int rt){
- sum[rt] = sum[rt<<1] + sum[rt<<1|1];
- nd[rt] = min(nd[rt<<1] , nd[rt<<1|1]);
- mx[rt] = max(mx[rt<<1], mx[rt<<1|1]);
- // lazy[rt] = lazy[rt<<1] + lazy[rt<<1|1];
- // lazy[rt<<1] = lazy[rt<<1|1] = 0;
- }
- void pushdown(int rt){
- if(lazy[rt]){
- lazy[rt<<1]+= lazy[rt];
- lazy[rt<<1|1] += lazy[rt];
- mx[rt<<1] +=lazy[rt];
- mx[rt<<1|1] +=lazy[rt];
- lazy[rt] = 0;
- }
- }
- void build(int l,int r,int rt){
- if(l==r){
- nd[rt] = b[l];
- lazy[rt] = mx[rt] = sum[rt] = 0;
- return;
- }
- int mid = (l+r)/2;
- 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 k){
- if(l>=L && r<=R)
- {
- mx[rt] ++;
- if(mx[rt] <nd[rt]){
- lazy[rt]++;
- return;
- }
- if(l==r){
- sum[rt]++;
- nd[rt]+=b[l];
- lazy[rt] = 0;
- return;
- }
- }
- int mid = (l+r)/2;
- pushdown(rt);
- if(mid>= L)update(l,mid,rt<<1,L,R,k);
- if(mid<R)update(mid+1,r,rt<<1|1,L,R,k);
- pushup(rt);
- }
- ll query(int l,int r,int rt,int L,int R){
- if(l>=L&&r<=R){
- return sum[rt];
- }
- int mid = (l+r)/2;
- // pushdown(rt);
- ll ans = 0;
- if(mid>= L)ans += query(l,mid,rt<<1,L,R);
- if(mid < R)ans += query(mid+1,r,rt<<1|1,L,R);
- return ans;
- }
- int main(){
- while(~scanf("%d%d", &n, &q)){
- for(int i=1; i<=n; i++){
- scanf("%d", &b[i]);
- }
- char s[20];
- build(1,n,1);
- for(int i=1; i<=q; i++){
- int l,r;
- scanf("%s%d%d", s, &l, &r);
- if(s[0]=='a'){
- update(1,n,1,l,r,0);
- // debug(a[5]);
- }
- else {
- ll ans = query(1,n,1,l,r);
- printf("%lld\n",ans);
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2701543.html