USACO 2021 US Open 铂金组 T1 题解
source link: https://blog-e.tk/2021/04/06/USACO-2021-US-Open-%E9%93%82%E9%87%91%E7%BB%84-T1-%E9%A2%98%E8%A7%A3/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
United Cows of Farmer John
给定一个长度为 n 的数列 ai，求符合下列条件的三元组 i,j,k 个数：
- 1≤i<j<k≤n
- ai,aj,ak 的值在 a[i,k] 各只出现一次（即他们自己）。
为了方便描述，我们称 ai 为 i 点的颜色，记 prei 表示 ai 的前驱（即 i 之前与 ai 相同的最后一个数），记集合 last 表示右端点扫描到 r 时，每个颜色最后一次出现的位置。
考虑固定右端点 r，然后枚举左端点 l 的位置，求此时 m 有多少种选择。发现答案即为 a[l+1,r−1] 中仅出现过一次的颜色数。
为了方便计算，我们可以使用代表元法。即随着 r 的向右推进，维护一个序列 appeari：
appeari={1(a[i+1,r]中没有与ai相同的颜色)−1(a[i+1,r]中恰有一个与ai相同的颜色)0(a[i+1,r]中有多于一个与ai相同的颜色)
具体的维护方式就是每当 r 右移到新的一位，就进行以下操作：
appear[i]++;
appear[pre[i]]-=2;
appear[pre[pre[i]]]++;
然后每次暴力枚举 l，并将后缀和加起来，我们就得到了一个 O(n2) 的做法。
注： 当然，在 r 固定的情况下，l 也是有限制的，即：l>pre[r] 并且 l∈last。
线段树优化
虽然在枚举 l 的时候有 l∈last 的限制，但是这个二重后缀求和仍有希望用数据结构维护。
记数组 sumappeari 表示以下的内容：
sumappeari={r−1∑j=i+1appearj(i∈last)0(i∉last)
则对 appeari 的修改可以转化为对 sumappear 前缀第 j(j∈last∩[1,i]) 位的修改。而枚举 l 的过程也可以转化为对 sumappear 第 j,j∈[prer+1,r−1] 的求和。
考虑用线段树维护这个信息，在每个节点上不仅要存区间的权值和，还要存一个 cnt 表示区间内有多少项在 last 集合里，每当 r 右移到新的一位，就将 sumappeari 的 cnt 设为 1，并将 sumappearprei 的 cnt 设为 0，给区间打 tag 时也按照 sum+=cnt*tag 加，于是这就是一个 O(nlogn) 的算法。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rd scanf
#define pt printf
#define setp(x) setprecision(x)
#define mem(x,y) memset(x,y,sizeof(x))
#define umn(x,y) x=min(x,y)
#define umx(x,y) x=max(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pi;
typedef queue<ll> qi;
typedef vector<ll> vi;
typedef vector<pi> vpi;
const ll INF=1e18;
const ll P=1e9+7;
const ll MXN=2e5+5;
inline ll mod(const ll &x){return x>=P?x-P:x;}
inline ll mul(ll x,ll y){if(x<y)swap(x,y);ll res=0;while(y){if(y&1)res=mod(res+x);x=mod(x<<1);y>>=1;}return res;}
inline ll qpow(ll x,ll y){ll res=1;while(y){if(y&1)res=res*x%P;x=x*x%P;y>>=1;}return res;}
ll gcd(const ll &x,const ll &y){return !y?x:gcd(y,x%y);}
inline void pbin(const ll &x,ll y){for(;~y;y--)cerr<<char('0'+((x>>y)&1));cerr<<endl;}
ll n,arr[MXN],res;
ll last[MXN],pre[MXN];
#define ls (p<<1)
#define rs (p<<1|1)
const ll NR=MXN<<2;
struct node{
ll va,sz,tag;
inline node(ll va=0,ll sz=0,ll tag=0):va(va),sz(sz),tag(tag){}
inline void addt(ll k){
tag+=k;
va+=sz*k;
}
inline node operator + (const node &y)const{return node(va+y.va,sz+y.sz);}
}t[NR];
inline void pushu(ll p){t[p]=t[ls]+t[rs];}
inline void pushd(ll p){
t[ls].addt(t[p].tag);
t[rs].addt(t[p].tag);
t[p].tag=0;
}
void build(ll p,ll l,ll r){
if(l==r){
t[p]=node(-2,1);
return;
}
ll mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
pushu(p);
}
void del(ll p,ll l,ll r,ll dx){
if(l==r){
t[p].sz=t[p].va=0;
return;
}
ll mid=(l+r)>>1;
pushd(p);
if(dx<=mid)del(ls,l,mid,dx);
else del(rs,mid+1,r,dx);
pushu(p);
}
void mod(ll p,ll l,ll r,ll ml,ll mr,ll mx){
if(ml<=l && r<=mr){
t[p].addt(mx);
return;
}
ll mid=(l+r)>>1;
pushd(p);
if(ml<=mid)mod(ls,l,mid,ml,mr,mx);
if(mr>mid)mod(rs,mid+1,r,ml,mr,mx);
pushu(p);
}
node que(ll p,ll l,ll r,ll ql,ll qr){
if(ql<=l && r<=qr)return t[p];
ll mid=(l+r)>>1;node res;
pushd(p);
if(ql<=mid)res=res+que(ls,l,mid,ql,qr);
if(qr>mid)res=res+que(rs,mid+1,r,ql,qr);
return res;
}
inline void solve(){
scanf("%lld",&n);
build(1,1,n);
for(int i=1;i<=n;i++){
scanf("%lld",arr+i);
pre[i]=last[arr[i]];
last[arr[i]]=i;
if(pre[i])del(1,1,n,pre[i]);
mod(1,1,n,1,i,1);
if(pre[i])mod(1,1,n,1,pre[i],-2);
if(pre[pre[i]])mod(1,1,n,1,pre[pre[i]],1);
if(pre[i]+2<=i)res+=que(1,1,n,pre[i]+1,i-1).va;
}
printf("%lld",res);
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
//ios_base::sync_with_stdio(0);cin.tie(0);
cout<<setiosflags(ios::fixed);
srand(time(NULL));
ll tq=1;
//cin>>tq;
while(tq--)solve();
return 0;
}
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量 87
v1.4.4
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK