Home Article Practice 分块维护最小值

分块维护最小值

2023-01-12 18:33  views:807  source:Coat    

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 510,M=200100,P=998274353,INF=0x3f3f3f3f;
int n, m, blo,a,b,c;
int v[N], bl[N], atag[N];
vector<int>ve[N];
void reset(int x)
{
ve[x].clear();
for (int i = (x - 1) * blo + 1; i <= min(x * blo, n); i++)
ve[x].push_back(v[i]);
sort(ve[x].begin(), ve[x].end());
}
void add(int a, int b, int c)
{
for (int i = a; i <= min(bl[a] * blo, b); i++)
v[i] += c;
reset(bl[a]);
if (bl[a] != bl[b])
{
for (int i = (bl[b] - 1) * blo + 1; i <= b; i++)
v[i] += c;
reset(bl[b]);
}
for (int i = bl[a] + 1; i <= bl[b] - 1; i++)
atag[i] += c;
}
int query(int a, int b, int c)
{
int ans = 0;
for (int i = a; i <= min(bl[a] * blo, b); i++)
if (v[i] + atag[bl[a]] < c)
ans++;
if (bl[a] != bl[b])
for (int i = (bl[b] - 1) * blo + 1; i <= b; i++)
if (v[i] + atag[bl[b]] < c)
ans++;
for (int i = bl[a] + 1; i <= bl[b] - 1; i++)
{
int x = c - atag[i];
ans += lower_bound(ve[i].begin(), ve[i].end(), x) - ve[i].begin();
}
return ans;
}
int main()
{
cin >> n >> m;
blo = sqrt(n);
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++)
bl[i] = (i - 1) / blo + 1, ve[bl[i]].push_back(v[i]);
for (int i = 1; i <= bl[n]; i++)
sort(ve[i].begin(), ve[i].end());
for (int i = 1; i <= m; i++)
{
char f; cin >> f;
cin >> a >> b >> c;
if (f == 'M')add(a, b, c);
else cout << b - a + 1 - query(a, b, c) << endl;
}
}



Disclaimer: The above articles are added by users themselves and are only for typing and communication purposes. They do not represent the views of this website, and this website does not assume any legal responsibility. This statement is hereby made! If there is any infringement of your rights, please contact us promptly to delete it.

字符:    改为:
去打字就可以设置个性皮肤啦!(O ^ ~ ^ O)