傳送門

文章目錄

• 題意
• 思路：

題意

有$n$個電臺，對于每個電臺$i$有三個參數$x_i,r_i,f_i$，分別指他們的坐標、作用半徑、頻率。如果兩個電臺頻率差值在$k$以內，并且他們的作用范圍都能覆蓋到彼此，那么稱這兩個電臺互相干擾，問這$n$個站臺中互相干擾的站臺有多少對。

$1\le n\le1e5,0\le k\le 10,1\le x_i,r_i\le 1e9,1\le f_i\le 1e4 $

思路：

首先將問題簡化一下，題面無非就是求滿足以下兩個條件的對數：

$(1)|x_i?x_j|\le min(r_i,r_j)$

$(2)|f_i?f_j|\le k$

看起來很$cdq$，考慮怎么分三維。

首先絕對值和取$min$肯定是要優先考慮的，并且如果我們確定了$r$的話，這個貌似就變成了個區間查詢的問題，所以我們第一維按照$r$從大到小排序，這樣$r$的值$[l,mid]>[mid+1,r]$，算左區間對右區間的貢獻的時候，左區間的$x_i$直接加入答案中，右區間貌似直接查詢一下$[x_j?r_j,x_j+r_j]$區間內的個數即可，離散化+樹狀數組完全可以解決，這樣我們就定下來了第三維。那么第二維就剩下$f$了，我們在第三維查詢區間內個數的時候，需要滿足$|f_i?f_j|\le k$，也就是說樹狀數組存下來的需要是合法的$f$，所以我們考慮整個指針代表的左區間$[x,i]$，由于第二維$f_i<f_j$成立，所以對于$f_j$我們需要保證$f_x+k>=f_j$最小的$x$即可，顯然這個具有單調性，動態維護一下。

但是很快你就會發現不對勁，因為$|f_i?f_j|\le k$是帶絕對值的！所以你只考慮左邊$\le f_j$是不對的，你還需要維護一個指針$y$，這個需要找到$f_y?k<=f_j$的最大的$y$位置。之后就得到了區間$[x,y]$，現在就可以查詢啦~

由于第二維保證有序，所以$j$右移的時候，$x,y$也是單調不減的，可以保證復雜度。

還有要注意，離散化的時候，離散化得到的$l,r$需要跟$i$下表綁定，也就是放到結構體里面，閑的沒事開了個數組存，結果$cdq$的時候改變了順序$wa$了半天。。。

復雜度$O(nlo{g}^{2}n)$

// Problem: E. Radio stations // Contest: Codeforces - Educational Codeforces Round 17 // URL: https://codeforces.com/problemset/problem/762/E // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") #define lowbit(x) (x&(-x)) using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,k; PII p[N]; int tr[N],se; LL ans; struct Node {int x,y,z,l,r;bool operator < (const Node &W) const {return mk(-x,mk(y,z))<mk(-W.x,mk(W.y,W.z));} }q[N],a[N]; vector<int>v;int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1; }void add(int x,int c) {for(int i=x;i<=se;i+=lowbit(i)) tr[i]+=c; }int sum(int x) {int ans=0;for(int i=x;i;i-=lowbit(i)) ans+=tr[i];return ans; }bool cmp(Node a,Node b) {return a.y<b.y; }void cdq(int l,int r) {if(l>=r) return;int mid=(l+r)>>1;cdq(l,mid); cdq(mid+1,r);int ls=l,rs=l;for(int i=mid+1;i<=r;i++) {while(ls<=mid&&q[ls].y+k<q[i].y) add(q[ls].z,-1),ls++;while(rs<=mid&&q[rs].y-k<=q[i].y) add(q[rs].z,1),rs++;ans+=sum(q[i].r)-sum(q[i].l-1);}while(ls<rs) add(q[ls].z,-1),ls++;int i=l,j=mid+1,cnt=0;while(i<=mid&&j<=r) {if(q[i].y<=q[j].y) a[++cnt]=q[i++];else a[++cnt]=q[j++];}while(i<=mid) a[++cnt]=q[i++];while(j<=r) a[++cnt]=q[j++];for(int i=1;i<=cnt;i++) q[l+i-1]=a[i]; }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) {int x,y,z; scanf("%d%d%d",&x,&y,&z);q[i]={y,z,x};v.pb(x-y); v.pb(x+y); v.pb(x);}sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());se=v.size();sort(q+1,q+1+n);for(int i=2;i<=n;i++) if(q[i].x==q[i-1].x&&q[i].y==q[i-1].y&&q[i].z==q[i-1].z) while(1);for(int i=1;i<=n;i++) {q[i].l=find(q[i].z-q[i].x),q[i].r=find(q[i].z+q[i].x);q[i].z=find(q[i].z);}cdq(1,n);cout<<ans<<endl;return 0; } /* k=1 r f x x y z 10 8 4 3 10 1 2 5 31 2 0** 1 3 1** 4 5 1** 1 5 3** */// #include <bits/stdc++.h> // using namespace std; // typedef long long ll; // #define rep(i, a, b) for(int i=(a), i##up=(b); i<=i##up; ++i) // #define repf(i, a) for(int i=1, i##up=(a); i<=i##up; ++i) // #define rrep(i, a, b) for(int i=(a), i##dn=(b); i>=i##dn; --i) // #define repe(e, u) for(int e=head[u]; e; e=nxt[e]) // // int read() {// int t=0, f=1; char c;// while(!isdigit(c=getchar())) f=c^45;// while(isdigit(c)) t=(t<<1)+(t<<3)+(c^48), c=getchar();// return f? t: -t; // } // // const int N=1e5+10, inf=1e9; // // int n, k; // ll ans; // // struct BIT {// #define lb(x) ((x)&-(x))// static const int X=3e5;// int c[X+10], tik[X+10], tim;// inline void modify(int x, int v=1) {// for(; x<=X; x+=lb(x)) if(tik[x]==tim) c[x]+=v; else tik[x]=tim, c[x]=v;// }// inline int query(int x, int v=0) {// for(; x; x^=lb(x)) if(tik[x]==tim) v+=c[x]; else tik[x]=tim, c[x]=0;// return v;// }// inline void clear() { tim++; } // }tre; // // int px[N*3], siz; // inline int find(int x) {// return lower_bound(px+1, px+1+siz, x)-px; // } // struct state {// int x, r, f, le, ri;// state() {}// state(int a, int b, int c): x(a), r(b), f(c) {}// inline void get() {// x=read(), r=read(), f=read();// le=x-r, ri=x+r;// px[++siz]=x, px[++siz]=le, px[++siz]=ri;// }// inline void reset() {// x=find(x), le=find(le), ri=find(ri);// } // }st[N]; // bool cmpr(state a, state b) {// if(a.r==b.r) return a.f<b.f||a.f==b.f&&a.x<b.x;// return a.r>b.r; // } // bool cmpf(state a, state b) {// return a.f<b.f; // } // // void sol(int le, int ri) {// if(le==ri) return;// int mid=le+ri>>1;// sol(le, mid), sol(mid+1, ri), tre.clear();// sort(st+le, st+mid+1, cmpf), sort(st+mid+1, st+ri+1, cmpf);// int pi_dn=le, pi_up=le, pj=mid+1;// while(pj<=ri) {// while(st[pj].f-st[pi_dn].f>k&&pi_dn<=mid) tre.modify(st[pi_dn++].x, -1);// while(st[pi_up].f-st[pj].f<=k&&pi_up<=mid) tre.modify(st[pi_up++].x);// ans+=tre.query(st[pj].ri)-tre.query(st[pj].le-1), pj++;// } // } // // int main() {// n=read(), k=read();// repf(i, n) st[i].get();// sort(px+1, px+1+siz), siz=unique(px+1, px+1+siz)-px-1;// repf(i, n) st[i].reset();// sort(st+1, st+1+n, cmpr);// sol(1, n);// printf("%lld", ans); // }

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 17 E. Radio stations cdq分治 + 树状数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。