My Blogs
P10550 [THUPC2024] 贸易
首先可以观察到，对于每种颜色，括号匹配（把 $0$ 看成左括号，$1$ 看成右括号）一定是最优的。所以可以先找出所有匹配 $[x,y]$，然后问题变成给定 $[l,r]$，求有多少个 $[x,y]\subseteq[l,r]$，离线做一遍扫描线，树状数组维护即可。
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
int n,m,a[500010],ans[500010],pre[500010];
vector<pii> ve[500010];
stack<int> st[500010];
namespace BIT
{
int t[500010];
inline void add(int x){for(;x;x-=x&-x)++t[x];}
inline int ask(int x){int s=0;for(;x<=n;x+=x&-x)s+=t[x];return s;}
}
using namespace BIT;
inline void mian()
{
read(n,m);int x,y;
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)
{
read(x);
if(a[i])
{
if(st[x].size())pre[i]=st[x].top(),st[x].pop();
}
else st[x].e(i);
}
for(int i=1;i<=m;++i)read(x,y),ve[y].eb(mp(x,i));
for(int i=1;i<=n;++i)
{
add(pre[i]);
for(auto p:ve[i])ans[p.se]=ask(p.fi);
}
for(int i=1;i<=m;++i)write(ans[i],'\n');
}