分块入门2: 区间修改+区间查询 小于 c元素的个数(vector 二分)_c++ 如何判断vector有几个元素小于某个值

题目链接：https://loj.ac/problem/6278
题目大意：

询问操作: 不完整的块枚举统计即可；而要在每个整块内寻找小于一个值的元素数，于是我们不得不要求块内元素是有序的，这样就能使用二分法对块内查询，需要预处理时每块做一遍排序，复杂度O(nlogn)，每次查询在√n个块内二分，以及暴力2√n个元素，总复杂度O(nlogn + n√nlog√n)。

每次修改，边块的vector必须重构。

必须在vector里面二分，不能改变原数组的位置。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标
#define LL(x) ((x-1)*Len+1)
const int maxn=5e5+5;
LL read()
{
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int a[50050], b[50050], add[505];//b[i]:i的块号
int Len, n;
vector<int> v[505];//每个块的元素

void reset(int x)//重构
{
    v[x].clear();
    for(int i=LL(x); i<=min(LL(x+1)-1, n); i++)
    {
        v[x].push_back(a[i]);
    }
    sort(v[x].begin(), v[x].end());
}

void Add(int L,int R,int x)
{
    int bL=b[L], bR=b[R];

    if(bL==bR)
    {
        for(int i=L;i<=R;i++)
        {
            a[i]+=x;
        }
        reset(bL);//边块修改完要重构
    }
    else
    {
        for(int i=L;i<LL(bL+1);i++)
        {
            a[i]+=x;
        }
        reset(bL);//边块修改完要重构

        for(int i=bL+1;i<bR;i++)
        {
            add[i]+=x;
        }

        for(int i=LL(bR);i<=R;i++)
        {
            a[i]+=x;
        }
        reset(bR);//边块修改完要重构
    }

}

int query(int L, int R, int x)
{
    int ans=0;
    int bL=b[L], bR=b[R];

    if(bL==bR)
    {
        for(int i=L;i<=R;i++)
        {
            if(a[i]+add[bL]<x)
            {
                ans++;
            }
        }
    }
    else
    {
        for(int i=L;i<LL(bL+1);i++)
        {
            if(a[i]+add[bL]<x)
            {
                ans++;
            }
        }

        for(int i=bL+1;i<bR;i++)
        {
            int f=x-add[i];
            ans+=lower_bound(v[i].begin(),v[i].end(), f)-v[i].begin();
        }

        for(int i=LL(bR);i<=R;i++)
        {
            if(a[i]+add[bR]<x)
            {
                ans++;
            }
        }
    }

    return ans;
}

void build(int n)
{
    Len=n/sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
        add[i]=0;
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=(i-1)/Len+1;
        v[b[i]].push_back(a[i]);
    }
    for(int i=1;i<=b[n];i++)
    {
        sort(v[i].begin(), v[i].end());
    }
}

int main()
{
    n=read();
    build(n);

    for(int i=1;i<=n;i++)
    {
        int op=read(), L=read(), R=read(), c=read();
        if(op==0)
        {
            Add(L, R, c);
        }
        else
        {
            printf("%d\n", query(L, R, c*c));
        }
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144