USACO二月月赛铂金组 friendcross CDQ分治+树状数组

2019-11-06 09:14:03

字体：大中小

来源：转载

供稿：网友

题目描述

PRoblem 3. 牛为何要过马路（三）道路两旁各有n个互不相同牧场，类型为a 的牛和类型为b的牛友好当且仅当 |a - b| ≤ K。给定路两旁的牧场，牛会穿过马路，去对⾯同类型的牧场。请算出有多少对相互不友好的牛的路径会相遇。n,k<=100 000

解法

诶最后280分，第一题少了20分，这题写出来也是蛮爽的。这道题最后大家的解法啥都有，树套树为主，我这种代码能力稍弱的人只好cdq分治硬上。将所有的相交统计出来，再容斥掉同组内的。区间移动的过程可以看成将第一个点拿走，再把最后一个点放上去，在统计一次答案，相当于两次修改一次查询，cdq分治按时间分治，一维分治时间，二维排序一个关键字，三维树状数组一个关键字就行了

#include <bits/stdc++.h>#define N 100050using namespace std;typedef long long LL;int n,k,a[N],b[N],d[N],p[N],cnt; LL ans = 0LL; inline int rd() { int r; scanf("%d",&r); return r; }struct BIT{ int tr[N]; inline int lowbit(int x) { return x & (-x); } inline void add(int x,int v) { for (int i=x;i<=n;i+=lowbit(i)) tr[i] += v; } inline int ask(int x) { int ret = 0; for (int i=x;i>=1;i-=lowbit(i)) ret += tr[i]; return ret; } inline void clear(int x) { for (int i=x;i<=n;i+=lowbit(i)) tr[i] = 0; }}T,T1,T2;struct Monster{ int t,l,r; }Q[4*N];bool cmp(Monster p1,Monster p2) { return p1.l == p2.l ? p1.r < p2.r : p1.l < p2.l; }inline void solve1() { for (int i=n;i>=1;i--) { ans += T.ask(d[ b[i] ]-1); T.add(d[b[i]],1); }}inline LL query1(int l,int r) { return T1.ask(r) - T1.ask(l-1); }inline LL query2(int l,int r) { return T2.ask(r) - T2.ask(l-1); }void cdq(int l,int r) { if (l >= r) return ; int mid = (l + r) >> 1; cdq(l,mid); cdq(mid+1,r); int p1 = l-1 , p2 = l-1; for (int _=mid;_>=l;_--) T2.add(Q[_].r , Q[_].t); for (int _=mid+1;_<=r;_++) if (Q[_].t == -1) { while (p1+1 <= mid && Q[p1+1].l < Q[_].l) { p1++; T1.add(Q[p1].r , Q[p1].t); } while (p2+1 <= mid && Q[p2+1].l <= Q[_].l) { p2++; T2.add(Q[p2].r , -Q[p2].t); } ans -= query1(Q[_].r+1,n); ans -= query2(1,Q[_].r-1); } for (int i=l;i<=mid;i++) T1.clear(Q[i].r) , T2.clear(Q[i].r); sort(Q+l,Q+r+1,cmp); //按l排序 }inline void solve2() { for (int i=1;i<=k+1;i++) Q[++cnt] = (Monster){1,p[i],d[i]}; for (int i=1;i<=n;i++) { Q[++cnt] = (Monster){-1,p[i],d[i]}; if (i+k+1 <= n) Q[++cnt] = (Monster){1,p[i+k+1],d[i+k+1]}; } cdq(1,cnt);}int main() { freopen("friendcross.in","r",stdin); freopen("friendcross.out","w",stdout); n = rd() , k = rd(); for (int i=1;i<=n;i++) a[i] = rd() , d[a[i]] = i; for (int i=1;i<=n;i++) b[i] = rd() , p[b[i]] = i; solve1(); solve2(); cout << ans << endl; return 0;}

上一篇：用户空间和内核空间、进程上下文和中断上下文

下一篇：Solr vs Elasticsearch vs Lucene