好题！
法1：看到题目，首先想到的便是树套树。按照一般想法，第一维是区间，第二维权值，不好想（至少我不会。。。据说有人这么干，orz）
如果反过来，做法就十分清晰了。对于区间[l,r]，将权值在此之内的修改建立一棵普通线段树。这样对于一个询问，就可以类似二分答案，首先看权值在[1,mid]中有几个在询问的区间中，如果<排名，就往右，否则往左。
/************************************************************** Problem: 3110 User: lazycal Language: C++ Result: Accepted Time:8436 ms Memory:201624 kb ****************************************************************/ #include <cstdio> const int N = 50000+9,M = N * 16 * 16; int root[N * 4],n,m,sum[M],lc[M],rc[M],lazy[M],c,L,R,cnt; inline int min(const int &a,const int &b){return a>b?b:a;} inline int max(const int &a,const int &b){return a>b?a:b;} int count(const int idx,const int l,const int r) { if (L <= l && r <= R) return sum[idx]; int t1 = 0,t2 = 0,mid = (l+r)/2; if (L <= mid) t1 = count(lc[idx],l,mid); if (mid < R) t2 = count(rc[idx],mid + 1,r); return (t1 + t2) + (min(r,R)-max(L,l) + 1) * lazy[idx]; } int query() { int l = 1, r = n, now = 1; for (;l != r;) { int mid = (l + r)/2, tmp; if ((tmp = count(root[now*2],1,n)) >= c) r = mid,now *= 2; else l = mid + 1,now = now*2 +1,c -= tmp; } return l; } void modify(int &idx,const int l,const int r) { if (!idx) idx = ++cnt; if (L <= l && r <= R) return (void)(sum[idx] += r - l + 1, ++lazy[idx]); int mid = (l + r)/2; if (L <= mid) modify(lc[idx],l,mid); if (mid < R) modify(rc[idx],mid + 1,r); sum[idx] = sum[lc[idx]] + sum[rc[idx]] + lazy[idx] * (r - l + 1); } void update() { int l = 1, r = n, now = 1; for (;l != r;) { int mid = (l + r)/2; modify(root[now],1,n); if (mid < c) l = mid + 1,now = now*2 + 1; else r = mid,now *= 2; } modify(root[now],1,n); } int main() { #ifndef ONLINE_JUDGE freopen("3110.in","r",stdin); freopen("3110.out","w",stdout); #endif scanf("%d%d",&n,&m); while (m--) { int flag; scanf("%d%d%d%d",&flag,&L,&R,&c); if (flag == 1) c = n - c + 1,update(); else printf("%d\n",n-query()+1); } }
法2：分治（orz）
同样是二分，令solve(l,r)代表解决ans = l...r的询问 （什么？我怎么知道ans在哪个区间？别急……），很明显，solve(1,n)即为所求。
对于solve(l,r)，任务就是将询问分组。分组等价于判断ans 与 (l+r)/2 的大小关系。也就是在[l,(l+r)/2]的数够不够k个。
处理这个问题，可以将要插入的数中<(l+r)/2的数插入到数据结构中，比如这个操作区间是L[i],R[i]，那就把L[i]...R[i]中每个数+1。这样判断ans 与 (l+r)/2 的大小关系时候直接在数据结构中查询，就可以得到在[l,(l+r)/2]的且在询问区间的数的个数。然后完成分组，solve(l,(l+r)/2) solve((l+r)/2+1,r)
对于数据结构的选择，个人推荐使用树状数组。不过得懂得树状数组如何改段求段。下面附上树状数组改段---->改点的推导：
delta[i] = A[i] - A[i - 1] {1 <= i <= n}Add(s,t,c): //A[s] += c; delta[s] = A[s] + c - A[s - 1] = delta[s] + c; delta[s] += c delta[s]*s += s*c //A[t] += c; delta[t + 1] = A[t + 1] - (A[t] + c) = delta[t + 1] - c; delta[t + 1] -= c delta[t + 1]*(t + 1) -= c*(t + 1)Sum(s,t,c): A[s] + ... + A[t] A[s] = A[s - 1] + delta[s] = A[s - 2] + delta[s] + delta[s - 1] = ... = delta[1] + ... + delta[s] A[s] + ... + A[t] = (delta[1] + ... + delta[s]) * (t - s + 1) + (t - s - i + 1) * delta[s + i] {1 <= i <= t - s} = (delta[1] + ... + delta[s]) * (t - s + 1) + (t + 1 - (s + i)) * delta[s + i] {1 <= i <= t - s}
/************************************************************** Problem: 3110 User: lazycal Language: C++ Result: Accepted Time:1560 ms Memory:3148 kb ****************************************************************/ #include <cstdio> const int N = 50000 + 9; int a1[2][N],a2[2][N],n,m,ans[N],a[N],b[N],c[N],tmp1[N],tmp2[N],times,t[N],flag[N]; int count(int (&data)[2][N],int x) { int res = 0; for (;x;x -= x & -x) if (data[0][x] == times) res += data[1][x]; return res; } void add(int (&data)[2][N],int x,const int d) { for (;x <= n;x += x & -x) if (data[0][x] == times) data[1][x] += d; else data[0][x] = times, data[1][x] = d; } int count(const int s,const int t) { return count(a1,s) * (t - s + 1) + (t + 1) * (count(a1,t) - count(a1,s)) - (count(a2,t) - count(a2,s)); } void add(const int s,const int t,const int c) { add(a1,s,c); add(a2,s,s*c); add(a1,t + 1,-c); add(a2,t + 1, -c*(t + 1)); } void solve(const int l1,const int r1,const int l,const int r) { if (l1 > r1) return ; if (l == r) { for (int i = l1; i <= r1; ++i) if (flag[t[i]] == 2) ans[t[i]] = l; return ; } int tmp; ++times; tmp1[0] = tmp2[0] = 0; const int mid = (l + r)/2; for (int i = l1; i <= r1; ++i) if (flag[t[i]] == 1) if (c[t[i]] <= mid) { tmp1[++tmp1[0]] = t[i]; add(a[t[i]],b[t[i]],1); }else tmp2[++tmp2[0]] = t[i]; else if ((tmp = count(a[t[i]],b[t[i]])) < c[t[i]]) { c[t[i]] -= tmp; tmp2[++tmp2[0]] = t[i]; }else tmp1[++tmp1[0]] = t[i]; int mid1 = tmp1[0] + l1 - 1; for (int i = l1; i <= mid1; ++i) t[i] = tmp1[i - l1 + 1]; for (int i = mid1 + 1; i <= r1; ++i) t[i] = tmp2[i - mid1]; solve(l1, mid1, l, mid); solve(mid1 + 1, r1, mid + 1, r); } int main() { #ifndef ONLINE_JUDGE freopen("3110_2.in","r",stdin); freopen("3110_2.out","w",stdout); #endif scanf("%d%d",&n,&m); for (int i = 1; i <= m; ++i) { scanf("%d%d%d%d",flag+i,a+i,b+i,c+i); if (flag[i] == 1) c[i] = n - c[i] + 1; t[i] = i; } solve(1,n,1,n); for (int i = 1; i <= m; ++i) if (flag[i] == 2) printf("%d\n",n-ans[i]+1); }
转载于:https://www.cnblogs.com/lazycal/p/3239304.html
