YZOJ P2967 收割
时间限制:4000MS 内存限制:524288KB
难度:\(7.0\)
-
题目描述
兔有 \(n\) 个甘蔗,兔将它们种成一排。
每天早上,第 \(i\) 个甘蔗会长高 \(a_i\) 米,但如果达到 \(b_i\) 米,就不会继续长高,而是维持在 \(b_i\) 米。
兔收割了 \(m\) 次甘蔗,第 \(i\) 次收割在第 \(t_i\) 天的晚上,他收割了 \([l_i, r_i]\) 中的所有甘蔗。收割后,这些甘蔗的高度变为 \(0\) 米,但第二天还会继续按照原来的规则生长。
请你求出兔每天收割了多少甘蔗。
-
输入格式
第一行 \(n, m\) ;
接下来 \(n\) 行,每一行 \(a_i, b_i\) ;
接下来 \(m\) 行,每一行 \(t_i, l_i, r_i\),保证输入的 \(t_i\) 严格递增。
-
输出格式
输出 \(m\) 行表示兔每次收割的甘蔗的高度之和。
-
样例输入
-
1234563 28 73 91 106 1 38 1 2
样例输出
1 2 |
22 13 |
-
数据规模与约定
存在 \(30\%\) 数据,保证所有甘蔗都不会长到 \(b_i\) 米;
存在 \(30\%\) 数据,保证每次收取的是所有萝卜;
存在 \(60\%\) 数据,\(n \leq 50000\);
对于所有数据 \(n \leq 300000\) ,\(m \leq 100000\) ,\(t_i,a_i,b_i \leq 10^9\) 。
首先麻烦的是每个(甘蔗=萝卜)的生长状态都是不一样的,可能有的已经成熟但是有的才刚被收割,直接维护有点麻烦。(其实是我不会)
发现每次操作都会把一段区间内的甘蔗全部收割,也就是生长状态清零,也就是区间推平(assign)操作。
都知道区间推平可以使用 ODT 来维护,也就是 std::set
维护上次收割时刻相同的区间,每次操作的时候把 \([l, r]\) 分割(split)成若干段分别计算答案,最后再推平即可。
剩下的问题就只有如何求出:生长了一段时间 \(\Delta t\) 后,区间内甘蔗的高度总和。
考虑 \(\lfloor \frac{b_i}{a_i} \rfloor\) ,它代表某一甘蔗成熟的时刻,在这个时刻及之前它的高度是 \(\Delta t \cdot a_i\) ,之后它的高度是 \(b_i\) 。
所以可以建立权值线段树,下标表示时刻(不离散化就会跑的跟我一样慢),要找到 \(\Delta t\) 时刻所有在线段树上的甘蔗的生长状态,可以在上面二分查找。
对于区间 \([l, r]\) :若 \(\Delta t \leq mid\) ,那么右区间 \((mid, r]\) 时刻内的甘蔗都没成熟,对 \(QA\) 贡献右区间内 \(a\) 的和,同时递归进左区间处理;若 \(\Delta t > mid\),那么左区间 \([l, mid]\) 时刻内的甘蔗都成熟了,对 \(QB\) 贡献左区间内 \(b\) 的和,同时递归进右区间处理。
特别注意的是 \(l = r = \Delta t\) 的情况,由于 \(\lfloor \frac{b_i}{a_i} \rfloor \leq \frac{b_i}{a_i}\) ,所以都按照未成熟的情况对 \(QA\) 贡献它的 \(a\) 。
所以本次询问的答案就是 \(\Delta t \cdot QA + QB\) 。
因为要求的是某一区间内甘蔗的生长高度和,所以建立主席树(或者说把权值线段树拿去可持久化)即可。
时间复杂度:大概是 \(O((n+m)\log n)\) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #ifdef ONLINE_JUDGE char __B[1<<15],*__S=__B,*__T=__B; #define getchar() (__S==__T&&(__T=(__S=__B)+fread(__B,1,1<<15,stdin),__S==__T)?EOF:*__S++) #endif inline int getnum() { register char c=0; while(!(c>='0' && c<='9')) c=getchar(); register int a=0; while(c>='0' && c<='9') a=a*10+c-'0',c=getchar(); return a; } struct _node { int l,r,t; }; struct _comp { bool operator ()(const _node&a,const _node&b) { return a.l < b.l; } }; int cnt,lson[10505050],rson[10505050]; long long mva[10505050],mvb[10505050]; #define _LMAX (1e9+1) int MP,MA,MB; void ModifyTree(int &o,register int oO,register int l=0,register int r=_LMAX) { o=++cnt; lson[o]=lson[oO],rson[o]=rson[oO]; if(l==r) { //printf("modify %d %d with %d %d\n",l,r,MA,MB); mva[o]=mva[oO]+MA,mvb[o]=mvb[oO]+MB; return; } register int mid=(l+r)>>1; if(MP <= mid) ModifyTree(lson[o],lson[oO],l,mid); else ModifyTree(rson[o],rson[oO],mid+1,r); mva[o]=mva[lson[o]]+mva[rson[o]],mvb[o]=mvb[lson[o]]+mvb[rson[o]]; } int QP; long long QA,QB; void QueryTree(register int o,register int oO,register int l=0,register int r=_LMAX) { if(!o && !oO) return; if(l==r) { QA+=mva[o]-mva[oO]; return; } register int mid=(l+r)>>1; if(QP <= mid) QA+=mva[rson[o]]-mva[rson[oO]],QueryTree(lson[o],lson[oO],l,mid); else QB+=mvb[lson[o]]-mvb[lson[oO]],QueryTree(rson[o],rson[oO],mid+1,r); } int a[305050],b[305050],t[305050]; int root[305050]; typedef __gnu_pbds::tree<_node,__gnu_pbds::null_type,_comp> _tt; typedef _tt::point_iterator _tit; _tt seg; inline _tit split(register int pos) { _tit it=seg.lower_bound((_node){pos,-1,0}); if(it!=seg.end() && it->l==pos) return it; --it; register int l=it->l,r=it->r,t=it->t; seg.erase(it); seg.insert((_node){l,pos-1,t}); return seg.insert((_node){pos,r,t}).first; } int main() { register int N=getnum(),M=getnum(); for(register int i=1;i<=N;i++) a[i]=getnum(),b[i]=getnum(),t[i]=(a[i] ? b[i]/a[i] : _LMAX); //printf("t[]= ");for(register int i=1;i<=N;i++) // printf("%d ",t[i]);printf("\n"); for(register int i=1;i<=N;i++) MP=t[i],MA=a[i],MB=b[i],ModifyTree(root[i],root[i-1]); seg.insert((_node){1,N,0}); for(register int lp=1;lp<=M;lp++) { long long ans=0; register int t=getnum(),l=getnum(),r=getnum(); _tit itr=split(r+1),itl=split(l); while(itl != itr) { register int dt=t - itl->t; //printf("update %d %d with %d\n",itl->l,itl->r,itl->t); QA=QB=0,QP=dt; QueryTree(root[itl->r],root[itl->l - 1]); ans+=(long long)dt*QA+QB; seg.erase(itl++); } seg.insert((_node){l,r,t}); printf("%lld\n",ans); } return 0; } |