[Educational Codeforces Round 17 E (762E)] Radio stations

题意

给出n个点，每个点有三围(x,r,f) 两个点是冲突的，当 |xi−xj|≤min(ri,rj)且|fi−fj|≤k . k 给出。 n≤105,0≤k≤10

题解

想法一： 按 x 从大到小枚举点，每次在kdtree中询问xj≤xi ri且xj−rj≤xi且|fj−fi|≤k的点的个数加入答案，再将 (xi,xi−ri,fi) 插入KDtree里。

觉得想法一要写起来好长，再想想

想法二： k 最大就10，对每一个f值建二维线段树，然后查询？

还是好长

想法三： CDQ啊！。。忘了怎么写了，感觉也不短

想法四： 对每一个 f 将x离散化，并建BIT，存储差分数据，来表示线段 (xi−ri,xi+ri) 的覆盖（ xi−ri 的地方插入1， xi+ri+1 的地方插入-1） 对所有点按照 xi 从大到小枚举，对 fi−k 到 fi+k 的BIT询问 xi 位置覆盖了几条线段，加入答案中。 同时将 xi−ri 记录下来，每次询问之前将 xj−rj<xi 的点都在相应的BIT中删去，这样就能保证每次询问合法了。

代码

/// by ztx /// blog.csdn.net/hzoi_ztx #define Rep(i,l,r) for(i=(l);i<=(r);i++) #define rep(i,l,r) for(i=(l);i< (r);i++) #define Rev(i,r,l) for(i=(r);i>=(l);i--) #define rev(i,r,l) for(i=(r);i> (l);i--) #define Each(i,v) for(i=v.begin();i!=v.end();i++) #define each(v) v.begin(),v.end() #define r(x) read(x) typedef long long ll ; typedef double lf ; int CH , NEG ; template <typename TP>inline void read(TP& ret) { ret = NEG = 0 ; while (CH=getchar() , CH<'!') ; if (CH == '-') NEG = true , CH = getchar() ; while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ; if (NEG) ret = -ret ; } #define maxn 100010LL #define maxf 10001LL struct DATA { int x, r, f; bool operator < (const DATA&B) const { return x < B.x; } } a[maxn]; struct BIT { int sum, n, *C; BIT(int n) { this->n = n, sum= 0; C = new int[n+1](); } inline int get(int p) { int ret = 0; for (; p; p -= (p&(-p))) ret += C[p]; return ret; } inline void inc(int p,int x) { sum += x; for (; p <= n; p += (p&(-p))) C[p] += x; } } *B[maxf]; std::vector<int>F[maxf]; std::multiset<DATA> S; inline void insert(int i,int x) { int p = lower_bound(each(F[a[i].f]), a[i].x)-F[a[i].f].begin()+1; B[a[i].f]->inc(p, x); } int main() { int n, K, i, j, fl, fr; ll ans; r(n), r(K); Rep (i,1,n) { r(a[i].x), r(a[i].r), r(a[i].f); F[a[i].f].push_back(a[i].x); } Rep (i,1,10000) { std::sort(each(F[i])); B[i] = new BIT(F[i].size()); } std::sort(a+1, a+n+1); ans = 0; Rep (i,1,n) { while (!S.empty() && S.begin()->x<a[i].x) insert(S.begin()->r,-1), S.erase(S.begin()); fl = std::max(1,a[i].f-K), fr = std::min(10000,a[i].f+K); Rep (j,fl,fr) ans += B[j]->sum - B[j]->get(lower_bound(each(F[j]),a[i].x-a[i].r)-F[j].begin()); insert(i,1); S.insert((DATA){a[i].x+a[i].r,i,0}); } printf("%lld\n", ans); END: getchar(), getchar(); return 0; }