分块（区间加法，寻找区间比k小的数的个数

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1e5+10;
 6 const int inf = 0x3f3f3f3f;
 7 int dir[10][10] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 8 int a[maxn], pos[maxn], opt, l, r, c, t, n, lz[maxn], ans;
 9 vector<int> v[600];
10 
11 inline int read()
12 {
13     char ch = getchar(); int k = 0, f = 1;
14     while(ch < '0' || ch > '9') {if(ch == '-')f = -1; ch = getchar();}
15     while(ch >= '0' && ch <= '9') {k = k * 10 + ch - '0'; ch = getchar();}
16     return k * f;
17 }
18 
19 inline void reset(int x)//由于加法更新了值 要更新vector数组
20 {
21     v[x].clear();
22     for(int i = (x - 1) * t + 1; i <= min(n, x * t); ++i)
23     {
24         v[x].push_back(a[i]);
25     }
26     sort(v[x].begin(), v[x].end());//块中数从小到大
27 }
28 
29 inline void inser(int l, int r, int c)
30 {
31     for(int i = l; i <= min(r, pos[l] * t); ++i) a[i] += c;
32     reset(pos[l]);
33     if(pos[l] != pos[r])
34     {
35         for(int i = (pos[r] - 1) * t + 1; i <= r; ++i) a[i] += c;
36         reset(pos[r]);
37     }
38     for(int i = pos[l] + 1; i <= pos[r] - 1; ++i) lz[i] += c;
39 }
40 
41 inline int findy(int l, int r, int c)
42 {
43     int ans = 0;
44     for(int i = l; i <= min(r, pos[l] * t); ++i)
45     {
46         if(a[i] + lz[pos[l]] < c) ans++;
47     }
48     if(pos[l] != pos[r])
49     {
50         for(int i = (pos[r] - 1) * t + 1; i <= r; ++i)
51         {
52             if(a[i] + lz[pos[r]] < c) ans++;
53         }
54     }
55 
56     for(int i = pos[l] + 1; i <= pos[r] - 1; ++i)
57     {
58         ans += lower_bound(v[i].begin(), v[i].end(), c - lz[i]) - v[i].begin();
59     }
60     return ans;
61 }
62 
63 int main()
64 {
65     n = read();
66     for(int i = 1; i <= n; ++i) cin>>a[i];
67     t = sqrt(n);
68     for(int i = 1; i <= n; ++i)
69     {
70         pos[i] = (i - 1) / t + 1;
71         v[pos[i]].push_back(a[i]);
72     }
73     for(int i = 1; i <= pos[n]; ++i)
74     {
75         sort(v[i].begin(), v[i].end());
76     }
77 
78     for(int i = 1; i <= n; ++i)
79     {
80         opt = read(); l = read(); r = read(); c = read();
81         if(opt == 0) inser(l, r, c);
82         else cout<<findy(l, r, c * c)<<endl;
83     }
84     return 0;
85 }
分块 （区间加法，寻找区间比k小的数的个数

分块（区间加法，寻找区间比k小的数的个数
