自动搬运

查看原文

来自洛谷，原作者为

	Lysea Please don't go away.

搬运于2025-08-24 23:03:47，当前版本为作者最后更新于2024-11-14 23:22:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种双指针二位偏序写法。

首先分三类讨论，将颜色 $0$、$1$、$2$ 分开来，避免多统计。

接着我们考虑将当前颜色矩阵与非当前颜色矩阵都按照 $l$ 从小到大排序，这样后满足 $l_i< l_j$ 的 $j$ 指针就可以做到单调不降了。

至于 $c_i>c_j$，用树状数组维护即可。

注意取模，注意不取等。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define INF 1e18
#define lowbit(x) (x&(-x))
using namespace std;
struct node{
	int l,w;
}e[N],d[N];
const int mx=1e5,M=1e9+7;
int n,l[N],w[N],c[N],cnte,cntd,t[N],ans;
bool cmp(node x,node y){
	return x.l<y.l;
}
void add(int x,int y){
	for(int i=x;i<=mx;i+=lowbit(i)) t[i]+=y;
}
int query(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i)) res+=t[i];
	return res;
}
void solve(int x){
	cnte=cntd=0;
	for(int i=1;i<=n;i++){
		if(c[i]==x) e[++cnte]={l[i],w[i]};
		else d[++cntd]={l[i],w[i]};
	}
	sort(d+1,d+cntd+1,cmp),sort(e+1,e+cnte+1,cmp);
	int j=1;
	for(int i=1;i<=cnte;i++){
		while(j<=cntd&&d[j].l<e[i].l) add(d[j].w,1),j++;
		ans=(ans+query(mx)-query(e[i].w))%M;
	}
	for(int i=1;i<j;i++) add(d[i].w,-1);
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>l[i]>>w[i]>>c[i];
	for(int T=0;T<=2;T++) solve(T);
	cout<<ans;
	return 0;
}