题目链接：https://vjudge.net/problem/UVA-12003
题意：n个数，每次查询[l,r]区间内比v小的数的个数，并且要更新一个位置为另一个值，强制在线。
首先分块，分块后对每一个块排序，查询遇到块的时候二分找比这个值小的，两端则枚举。
更新的时候，修改一个值，冒泡就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 300100; 6 int n, q, sz, be[maxn]; 7 LL u, a[maxn]; 8 vector<LL> block[maxn]; 9 10 LL query(int l, int r, LL v) { 11 LL ret = 0; 12 for(int i = l; i <= r; ) { 13 if(i % sz == 0 && i + sz <= r) { 14 ret += lower_bound(block[be[i]].begin(), block[be[i]].end(), v) - block[be[i]].begin(); 15 i += sz; 16 } 17 else { 18 if(a[i] < v) ret++; 19 i++; 20 } 21 } 22 return ret; 23 } 24 25 void update(int p, LL v) { 26 int pre = a[p]; 27 a[p] = v; 28 vector<LL>& b = block[be[p]]; 29 int pos = 0; 30 while(b[pos] < pre) pos++; 31 b[pos] = v; 32 if(v > pre) { 33 while(pos < b.size() - 1 && b[pos] > b[pos+1]) { 34 swap(b[pos+1], b[pos]); 35 pos++; 36 } 37 } 38 else { 39 while(pos > 0 && b[pos] < b[pos-1]) { 40 swap(b[pos-1], b[pos]); 41 pos--; 42 } 43 } 44 } 45 46 int main() { 47 // freopen("in", "r", stdin); 48 int l, r, p; 49 LL v; 50 while(~scanf("%d%d%d",&n,&q,&u)) { 51 sz = sqrt((double)n); 52 for(int i = 0; i < n; i++) block[i].clear(); 53 for(int i = 0; i < n; i++) { 54 scanf("%d", &a[i]); 55 be[i] = i / sz; 56 block[be[i]].push_back(a[i]); 57 } 58 for(int i = 0; i <= sz; i++) { 59 sort(block[i].begin(), block[i].end()); 60 } 61 while(q--) { 62 scanf("%d%d%lld%d",&l,&r,&v,&p); 63 l--; r--; p--; 64 LL k = query(l, r, v); 65 update(p, k*u/(r-l+1)); 66 } 67 for(int i = 0; i < n; i++) { 68 printf("%lld ", a[i]); 69 } 70 } 71 return 0; 72 }