题目：传送门
题意：
给你n个数，要进行m次操作
对于每次操作(l,r,v,p)代表：在区间[l,r]中有x(这个x是需要你自己找出来的)个数小于v，你需要把序列的第p个位置的值改成u∗k/(r−l + 1)
最后输出序列就完了
题解：
因为他要找出来区间中有多少数小于v，所以我们就要维护一个数组a，在这个a数组里面要放置每一块排序后的结束(我的代码是从小到大排序)。为什么要排序，因为对于一个序列排完序之后我们可以通过二分找出来小于v的那个数的位置，然后我们又知道每一个块的左区间位置和右区间位置，所以可以很简单求出来x的值
具体操作见代码：
1 #include <iostream>
2 #include<stdio.h>
3 #include<string.h>
4 #include<algorithm>
5 #include<math.h>
6 using namespace std;
7 const int maxn=300005;
8 int a[maxn],L[maxn],R[maxn],belong[maxn],b[maxn];
9 int l,r,v,p,n,m,u;
10 void build()
11 {
12 int len=sqrt(n);
13 int ci=n/len;
14 for(int i=1; i<=ci; ++i)
15 {
16 L[i]=len*(i-1)+1;
17 R[i]=len*i;
18 }
19 R[ci]=n;
20
21 for(int i=1; i<=ci; ++i)
22 {
23 for(int j=L[i]; j<=R[i]; ++j)
24 {
25 belong[j]=i;
26 }
27 sort(a+L[i],a+R[i]+1);
28 }
29 }
30 int query()
31 {
32 int ans=0;
33 if(belong[l]==belong[r])
34 {
35 for(int i=l; i<=r; ++i)
36 {
37 if(b[i]<v) ans++;
38 }
39 }
40 else
41 {
42 for(int i=l; i<=R[belong[l]]; i++) ans+=b[i]<v;
43 for(int i=belong[l]+1; i<belong[r]; i++)
44 ans+=lower_bound(a+L[i],a+R[i]+1,v)-a-L[i];
45 for(int i=L[belong[r]]; i<=r; i++) ans+=b[i]<v;
46 }
47 return ans;
48 }
49 void update(int x)
50 {
51 int pos=lower_bound(a+L[belong[p]],a+R[belong[p]]+1,b[p])-a;
52 x=(long long)u*x/(r-l+1);
53 a[pos]=x;
54 if(b[p]>x)
55 {
56
57 for(int i=pos; i>L[belong[p]]; i--)
58 {
59 if(a[i]<a[i-1]) swap(a[i],a[i-1]);
60 else break;
61 }
62 }
63 else if(b[p]<x)
64 {
65
66 for(int i=pos; i<R[belong[p]]; i++)
67 {
68 if(a[i]>a[i+1]) swap(a[i],a[i+1]);
69 else break;
70 }
71 }
72 b[p]=x;
73 }
74 int main()
75 {
76
77 while(~scanf("%d%d%d",&n,&m,&u))
78 {
79 for(int i=1; i<=n; ++i)
80 scanf("%d",&a[i]),b[i]=a[i];
81 build();
82 while(m--)
83 {
84 scanf("%d%d%d%d",&l,&r,&v,&p);
85 update(query());
86 }
87 for(int i=1; i<=n; ++i)
88 {
89 printf("%d\n",b[i]);
90 }
91 }
92 return 0;
93 }
94 /*
95 10 1 11
96 1
97 2
98 3
99 4
100 5
101 6
102 7
103 8
104 9
105 10
106 2 8 6 10
107 */