「USACO 2021 US Open Platinum」United Cows of Farmer John

Posted on Edited on In

「USACO 2021 US Open Platinum」United Cows of Farmer John

考虑依次枚举右端点 \(i\) ，计算左边合法的方案数，设一个数 \(x\) 上次出现的位置为 \(lst_x\)

则 \(i\) 能够作为右端点的区间就是 \([lst_{a_i}+1,i-2]\)

考虑什么样的位置可以作为左端点，显然这个点在 \([1,i]\) 中是最后一次出现

我们将不妨这样的点权值设为 \(w_i=1\)

考虑一个点作为中间点贡献怎样的区间，同样的，这个点在 \([1,i]\) 中是最后一次出现

并且，能够贡献的区间 \(>\) 上一次出现的位置 \(lst_x\)

这个中间点能够匹配的左端点个数就是 \(\displaystyle \sum_{k=lst_{a_j}+1}^{j-1} w_k\)

现在我们要用数据结构动态修改某一个位置的 \(w_i\) ，增减 \([lst_{a_j}+1,j-1]\) 的区间，查询 \([lst_{a_i}+1,i-2]\)

不妨再为一个点增加点权 \(t_i\) ，此时我们要维护的操作

1.单点修改 \(w_i\)

2.区间修改 \(t_i\)

3.求 \(w_it_i\) 区间和

在线段树上每个节点维护 \(w_i\) 之和， \(w_it_i\) 之和，可以标记永久化 \(t_i\)

具体实现参考代码（实际写得很丑）

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int N=2e5+10,INF=1e9+10;


int n;
int lst[N],lst2[N],cnt;
ll s1[N<<2],s2[N<<2];
int t[N<<2];
// s1表示w之和，s2表示区间内部t[i]*w[i]之和，t[i]现在是永久化的标记
void Up(int p){
	s2[p]=s2[p<<1]+s2[p<<1|1];
	s1[p]=s1[p<<1]+s1[p<<1|1]+s2[p]*t[p];
}
void Upd(int p,int l,int r,int x){
	if(l==r) {
		s2[p]^=1,s1[p]=t[p]*s2[p];
		return;
	}
	int mid=(l+r)>>1;
	x<=mid?Upd(p<<1,l,mid,x):Upd(p<<1|1,mid+1,r,x);
	Up(p);
}

void Upd(int p,int l,int r,int ql,int qr,int x){
	if(ql>qr) return;
	if(ql<=l && r<=qr) {
		t[p]+=x,s1[p]+=x*s2[p];
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
	Up(p);
}

struct Node{
	ll x,y;
	Node(ll x=0,ll y=0):x(x),y(y){  }
	Node operator + (const Node __) { return Node(x+__.x,y+__.y); }
};
Node Que(int p,int l,int r,int ql,int qr){
	if(ql>qr) return Node();
	if(ql<=l && r<=qr) return Node(s1[p],s2[p]);
	int mid=(l+r)>>1; Node res;
	if(ql<=mid) res=res+Que(p<<1,l,mid,ql,qr);
	if(qr>mid) res=res+Que(p<<1|1,mid+1,r,ql,qr);
	res.x+=res.y*t[p];
	return res;
}

int main(){
	n=rd();
	ll ans=0;
	rep(i,1,n) {
		int x=rd();
		if(lst[x]) {
			Upd(1,1,n,lst[x]),cnt--;
			Upd(1,1,n,lst2[x]+1,lst[x],-1);
		}
		Node t=Que(1,1,n,lst[x]+1,i-2);
		ans+=t.x;
		Upd(1,1,n,i),cnt++,Upd(1,1,n,lst[x]+1,i-1,1);
		lst2[x]=lst[x],lst[x]=i;
	}
	printf("%lld\n",ans);
}