序列是 1 inf 1 inf 1 inf……这样构造是不是就挂了
by bamboo1030 @ 2024-03-27 16:13:04
@[bamboo1030](/user/369181) 应该不会挂吧，因为我维护了次大值，可以直接返回最大值个数
by hh20080501hh @ 2024-03-27 16:22:42
@[hh20080501hh](/user/588201) 那我稍微弄一下呗
1 inf 2 inf-1 3 inf-3……
by bamboo1030 @ 2024-03-27 16:28:44
打错了是 inf-2 但是大概是那个意思
by bamboo1030 @ 2024-03-27 16:29:08
附上代码，方便大家卡我QAQ
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10 , INF = 1e9;
int n , m;
int a[N];
struct node
{
int l , r;
int mx , semx , cntmx;
int mn , semn , cntmn;
int add;
}tr[N<<2];
void pushup (node &rt , node l , node r)
{
if (l.mx==r.mx) //处理最大值
{
rt.mx = l.mx , rt.cntmx = l.cntmx+r.cntmx;
rt.semx = max(l.semx , r.semx);
}
else if (l.mx>r.mx)
{
rt.mx = l.mx , rt.cntmx = l.cntmx;
rt.semx = max(l.semx , r.mx);
}
else
{
rt.mx = r.mx , rt.cntmx = r.cntmx;
rt.semx = max(r.semx , l.mx);
}
if (l.mn==r.mn) //处理最小值
{
rt.mn = l.mn , rt.cntmn = l.cntmn+r.cntmn;
rt.semn = min(l.semn , r.semn);
}
else if (l.mn<r.mn)
{
rt.mn = l.mn , rt.cntmn = l.cntmn;
rt.semn = min(l.semn , r.mn);
}
else
{
rt.mn = r.mn , rt.cntmn = r.cntmn;
rt.semn = min(r.semn , l.mn);
}
}
void pushup (int u)
{
pushup (tr[u] , tr[u<<1] , tr[u<<1|1]);
}
void build (int u , int l , int r)
{
if (l==r)
{
tr[u] = {l , r , a[l] , -INF , 1 , a[l] , INF , 1 , 0};
}
else
{
tr[u].l = l , tr[u].r = r;
int mid = (l+r)>>1;
build (u<<1 , l , mid) , build (u<<1|1 , mid+1 , r);
pushup (u);
}
}
void update (int u , int c) //偷懒少写几次更新
{
tr[u].add += c;
tr[u].mn += c , tr[u].mx += c;
tr[u].semn += c , tr[u].semx += c;
}
void pushdown (int u)
{
if (tr[u].add)
{
update (u<<1 , tr[u].add) , update (u<<1|1 , tr[u].add);
tr[u].add = 0;
}
}
void modify (int u , int l , int r , int c)
{
if (tr[u].l>=l && tr[u].r<=r)
{
update (u , c);
}
else
{
pushdown (u);
int mid = (tr[u].l+tr[u].r)>>1;
if (l<=mid)
{
modify (u<<1 , l , r , c);
}
if (r>mid)
{
modify (u<<1|1 , l , r , c);
}
pushup (u);
}
}
int query (int u , int l , int r , int c)
{
if (tr[u].l>=l && tr[u].r<=r)
{
if (tr[u].mn>=c) return tr[u].r-tr[u].l+1;
if (tr[u].mx<c) return 0;
if (tr[u].mx>=c && tr[u].semx<c) return tr[u].cntmx;
if (tr[u].mn<c && tr[u].semn>=c) return tr[u].r-tr[u].l+1-tr[u].cntmn;
}
pushdown (u);
int mid = (tr[u].l+tr[u].r)>>1;
int res = 0;
if (l<=mid)
{
res += query (u<<1 , l , r , c);
}
if (r>mid)
{
res += query (u<<1|1 , l , r , c);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i=1 ; i<=n ; i++)
{
cin >> a[i];
}
build (1 , 1 , n);
while (m--)
{
string s;
int l , r , c;
cin >> s >> l >> r >> c;
if (s=="A")
{
cout << query (1 , l , r , c) << '\n';
}
else
{
modify (1 , l , r , c);
}
}
return 0;
}
```
by hh20080501hh @ 2024-03-27 16:29:28
@[bamboo1030](/user/369181) 稍等一下，我拍一下试试
by hh20080501hh @ 2024-03-27 16:32:36
@[bamboo1030](/user/369181) 确实被卡掉了，跑了3s
by hh20080501hh @ 2024-03-27 16:40:40
@[hh20080501hh](/user/588201) 主要是你这个其实递归的层数没有保证啊和区间颜色数挂钩的 所以其实如果你按上面的序列全部询问 [1, n] 会卡满
by bamboo1030 @ 2024-03-27 16:43:56
直接退化 O(n)
by bamboo1030 @ 2024-03-27 16:44:29
@[bamboo1030](/user/369181) 也就是说这道题必须用分块吗？
by hh20080501hh @ 2024-03-27 16:46:39