4293: [PA2015]Siano
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 546 Solved: 188 [Submit][Status][Discuss]Description
农夫Byteasar买了一片n亩的土地，他要在这上面种草。
他在每一亩土地上都种植了一种独一无二的草，其中，第i亩土地的草每天会长高a[i]厘米。 Byteasar一共会进行m次收割，其中第i次收割在第d[i]天，并把所有高度大于等于b[i]的部分全部割去。Byteasar想知道，每次收割得到的草的高度总和是多少，你能帮帮他吗？Input
第一行包含两个正整数n,m(1<=n,m<=500000)，分别表示亩数和收割次数。
第二行包含n个正整数，其中第i个数为a，依次表示每亩种植的草的生长能力。 接下来m行，每行包含两个正整数d[i],b，依次描述每次收割。 数据保证d[1]<d[2]<...<d[m]，并且任何时刻没有任何一亩草的高度超过10^12。Output
输出m行，每行一个整数，依次回答每次收割能得到的草的高度总和。
Sample Input
4 4
1 2 4 3
1 1
2 2
3 0
4 4
Sample Output
6
6
18
0
HINT
第1天，草的高度分别为1,2,4,3，收割后变为1,1,1,1。
第2天，草的高度分别为2,3,5,4，收割后变为2,2,2,2。
第3天，草的高度分别为3,4,6,5，收割后变为0,0,0,0。
第4天，草的高度分别为1,2,4,3，收割后变为1,2,4,3。
Source
By Claris
题解
此题卡常，疯狂TLE，最终没过，但是在洛谷团队里过了，正确性有保证。
首先按照a排序，发现不管怎么割草的长度都是单调的。 这样我们就很容易二分的找到割的位置，查询长度和，并修改即可。 用线段树。 记录 区间内最晚的最近一次被割的草被割时间为last ，到last时间区间内草长度和sum ，区间是否被割标记，到last时间最短的草的长度#include#include #include #include #include #include #include #include #include #include #define max(a, b) ((a) > (b) ? (a) : (b))#define min(a, b) ((a) < (b) ? (a) : (b))#define abs(x) ((x) < 0 ? -1 * (x) : (x))template inline void swap(T &x, T &y){ T tmp = x;x = y, y = tmp;} template inline void read(T &x){ x = 0;char ch = getchar(), c = ch; while(ch < '0' || ch > '9') c = ch, ch = getchar(); while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); if(c == '-') x = -x;}const int INF = 0x3f3f3f3f;const int MAXN = 1000000 + 10;long long n,m,a[MAXN],d[MAXN],b[MAXN];struct Node{ //区间内最晚的最近一次被割的草被割时间为last，到last时间区间内草长度和sum //lazy表示区间是否被割 //mi表示到last时间最短的草的长度 long long sum, last, mi; int lazy; int l,r; Node(){l = r = -1;lazy = sum = last = mi = 0;}}node[MAXN << 2];void pushdown(int o){ if(node[o].lazy) { node[o << 1].last = node[o << 1 | 1].last = node[o].last; long long tmp = node[o].sum / (node[o].r - node[o].l + 1); node[o << 1].sum = tmp * (node[o << 1].r - node[o << 1].l + 1); node[o << 1 | 1].sum = tmp * (node[o << 1 | 1].r - node[o << 1 | 1].l + 1); node[o << 1].lazy = node[o << 1 | 1].lazy = 1; node[o << 1].mi = node[o << 1 | 1].mi = tmp; node[o].lazy = 0; }} Node merge(Node x,Node y){ if(x.l == -1) return y; if(y.l == -1) return x; Node re; re.l = x.l, re.r = y.r; if(x.last > y.last) swap(x, y); re.mi = x.mi + (y.last - x.last) * (a[x.l] - a[x.l - 1]); re.sum = x.sum + y.sum + (y.last - x.last) * (a[x.r] - a[x.l - 1]); re.last = y.last; return re;}void build(int o = 1, int l = 1, int r = n){ node[o].l = l, node[o].r = r; if(l == r) return; int mid = (l + r) >> 1; build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);}void modify(int ll, int rr, int k, int o = 1, int l = 1, int r = n){ pushdown(o); if(ll <= l && rr >= r) { node[o].lazy = 1; node[o].last = d[k], node[o].sum = b[k] * (node[o].r - node[o].l + 1), node[o].mi = b[k]; return; } int mid = (l + r) >> 1; if(mid >= ll) modify(ll, rr, k, o << 1, l, mid); if(mid < rr) modify(ll, rr, k, o << 1 | 1, mid + 1, r); node[o] = merge(node[o << 1], node[o << 1 | 1]); return;}Node ask(int ll, int rr, int o = 1, int l = 1, int r = n){ pushdown(o); if(ll <= l && rr >= r) return node[o]; int mid = (l + r) >> 1; Node a,b; if(mid >= ll) a = ask(ll, rr, o << 1, l, mid); if(mid < rr) b = ask(ll, rr, o << 1 | 1, mid + 1, r); node[o] = merge(node[o << 1], node[o << 1 | 1]); Node re = merge(a, b); return re;}int find(int k, int o = 1, int l = 1, int r = n){ pushdown(o); if(l == r) { if(b[k] <= node[o].mi + (a[node[o].l] - a[node[o].l - 1]) * (d[k] - node[o].last)) return l; else return -1; } int mid = (l + r) >> 1,re; if(node[o << 1 | 1].mi + (a[node[o << 1 | 1].l] - a[node[o << 1 | 1].l - 1]) * (d[k] - node[o << 1 | 1].last) >= b[k]) { re = mid + 1; int tmp = find(k, o << 1, l, mid); if(tmp != -1) re = tmp; } else re = find(k, o << 1 | 1, mid + 1, r); node[o] = merge(node[o << 1], node[o << 1 | 1]); return re;}std::string s;int stack[1000],top;int main(){ read(n), read(m); register int i; n -= 4; for(i = 1;i <= n;i += 4) { read(a[i]); read(a[i + 1]); read(a[i + 2]); read(a[i + 3]); } n += 4; for(;i <= n;++ i) read(a[i]); std::sort(a + 1, a + 1 + n); n -= 4; for(i = 1;i <= n;i += 4) { a[i] += a[i - 1]; a[i + 1] += a[i]; a[i + 2] += a[i + 1]; a[i + 3] += a[i + 2]; } n += 4; for(;i <= n;++ i)a[i] += a[i - 1]; m -= 4; for(i = 1;i <= m;i += 4) { read(d[i]), read(b[i]); read(d[i + 1]), read(b[i + 1]); read(d[i + 2]), read(b[i + 2]); read(d[i + 3]), read(b[i + 3]); } m += 4; for(;i <= m;++ i) read(d[i]), read(b[i]); build(); for(i = 1;i <= m;++ i) { int ans = 0; Node tmp; ans = find(i); if(ans <= 0) { s += '0'; s += '\n'; continue; } tmp = ask(ans, n); long long tmp2 = tmp.sum + (a[n] - a[ans - 1]) * (d[i] - tmp.last) - (n - ans + 1) * b[i]; char c;top = 0; if(tmp2 == 0) s += '0'; while(tmp2) stack[++ top] = tmp2%10, tmp2 /= 10; while(top) s += stack[top --] + '0'; s += '\n'; modify(ans, n, i); } std::cout << s; return 0;}