[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}); }