My Blogs

P10550 [THUPC2024] 贸易

首先可以观察到，对于每种颜色，括号匹配（把 \(0\) 看成左括号，\(1\) 看成右括号）一定是最优的。所以可以先找出所有匹配 \([x,y]\)，然后问题变成给定 \([l,r]\)，求有多少个 \([x,y]\subseteq[l,r]\)，离线做一遍扫描线，树状数组维护即可。

	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');
	}