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

2019-11-14 09:34:23

字体：大中小

来源：转载

供稿：网友

题意

题解

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

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

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

还是好长

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

想法四：对每一个f $f$ 将x $x$ 离散化，并建BIT，存储差分数据，来表示线段(xi−ri,xi+ri) $(x_i-r_i,x_i+r_i)$ 的覆盖（xi−ri $x_i-r_i$ 的地方插入1，xi+ri+1 $x_i+r_i+1$ 的地方插入-1）对所有点按照xi $x_i$ 从大到小枚举，对fi−k $f_i-k$ 到fi+k $f_i+k$ 的BIT询问xi $x_i$ 位置覆盖了几条线段，加入答案中。同时将xi−ri $x_i-r_i$ 记录下来，每次询问之前将xj−rj<xi $x_j-r_j < x_i$ 的点都在相应的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 10001LLstruct 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;}

上一篇：python的functools进阶模块

下一篇：1060. Are They Equal (25)