公司的网站建设费入什么科目,seo短视频永久入口运营,上海公司免费起名,一线城市做网站工资有多少钱传送门 文章目录题意思路#xff1a;题意
有nnn个电台#xff0c;对于每个电台iii有三个参数xi,ri,fix_i,r_i,f_ixi,ri,fi#xff0c;分别指他们的坐标、作用半径、频率。如果两个电台频率差值在kkk以内#xff0c;并且他们的作用范围都能覆盖到彼此#xff0c;那么…传送门 文章目录题意思路题意
有nnn个电台对于每个电台iii有三个参数xi,ri,fix_i,r_i,f_ixi,ri,fi分别指他们的坐标、作用半径、频率。如果两个电台频率差值在kkk以内并且他们的作用范围都能覆盖到彼此那么称这两个电台互相干扰问这nnn个站台中互相干扰的站台有多少对。
$1\le n\le1e5,0\le k\le 10,1\le x_i,r_i\le 1e9,1\le f_i\le 1e4 $
思路
首先将问题简化一下题面无非就是求满足以下两个条件的对数
(1)∣xi−xj∣≤min(ri,rj)(1)|x_i-x_j|\le min(r_i,r_j)(1)∣xi−xj∣≤min(ri,rj)
(2)∣fi−fj∣≤k(2)|f_i-f_j|\le k(2)∣fi−fj∣≤k
看起来很cdqcdqcdq考虑怎么分三维。
首先绝对值和取minminmin肯定是要优先考虑的并且如果我们确定了rrr的话这个貌似就变成了个区间查询的问题所以我们第一维按照rrr从大到小排序这样rrr的值[l,mid][mid1,r][l,mid][mid1,r][l,mid][mid1,r]算左区间对右区间的贡献的时候左区间的xix_ixi直接加入答案中右区间貌似直接查询一下[xj−rj,xjrj][x_j-r_j,x_jr_j][xj−rj,xjrj]区间内的个数即可离散化树状数组完全可以解决这样我们就定下来了第三维。那么第二维就剩下fff了我们在第三维查询区间内个数的时候需要满足∣fi−fj∣≤k|f_i-f_j|\le k∣fi−fj∣≤k也就是说树状数组存下来的需要是合法的fff所以我们考虑整个指针代表的左区间[x,i][x,i][x,i]由于第二维fifjf_if_jfifj成立所以对于fjf_jfj我们需要保证fxkfjf_xkf_jfxkfj最小的xxx即可显然这个具有单调性动态维护一下。
但是很快你就会发现不对劲因为∣fi−fj∣≤k|f_i-f_j|\le k∣fi−fj∣≤k是带绝对值的所以你只考虑左边≤fj\le f_j≤fj是不对的你还需要维护一个指针yyy这个需要找到fy−kfjf_y-kf_jfy−kfj的最大的yyy位置。之后就得到了区间[x,y][x,y][x,y]现在就可以查询啦~
由于第二维保证有序所以jjj右移的时候x,yx,yx,y也是单调不减的可以保证复杂度。
还有要注意离散化的时候离散化得到的l,rl,rl,r需要跟iii下表绑定也就是放到结构体里面闲的没事开了个数组存结果cdqcdqcdq的时候改变了顺序wawawa了半天。。。
复杂度O(nlog2n)O(nlog^2n)O(nlog2n)
// 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,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-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];
vectorintv;int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()1;
}void add(int x,int c) {for(int ix;ise;ilowbit(i)) tr[i]c;
}int sum(int x) {int ans0;for(int ix;i;i-lowbit(i)) anstr[i];return ans;
}bool cmp(Node a,Node b) {return a.yb.y;
}void cdq(int l,int r) {if(lr) return;int mid(lr)1;cdq(l,mid); cdq(mid1,r);int lsl,rsl;for(int imid1;ir;i) {while(lsmidq[ls].ykq[i].y) add(q[ls].z,-1),ls;while(rsmidq[rs].y-kq[i].y) add(q[rs].z,1),rs;anssum(q[i].r)-sum(q[i].l-1);}while(lsrs) add(q[ls].z,-1),ls;int il,jmid1,cnt0;while(imidjr) {if(q[i].yq[j].y) a[cnt]q[i];else a[cnt]q[j];}while(imid) a[cnt]q[i];while(jr) a[cnt]q[j];for(int i1;icnt;i) q[li-1]a[i];
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d%d,n,k);for(int i1;in;i) {int x,y,z; scanf(%d%d%d,x,y,z);q[i]{y,z,x};v.pb(x-y); v.pb(xy); v.pb(x);}sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());sev.size();sort(q1,q1n);for(int i2;in;i) if(q[i].xq[i-1].xq[i].yq[i-1].yq[i].zq[i-1].z) while(1);for(int i1;in;i) {q[i].lfind(q[i].z-q[i].x),q[i].rfind(q[i].zq[i].x);q[i].zfind(q[i].z);}cdq(1,n);coutansendl;return 0;
}
/*
k1
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); ii##up; i)
// #define repf(i, a) for(int i1, i##up(a); ii##up; i)
// #define rrep(i, a, b) for(int i(a), i##dn(b); ii##dn; --i)
// #define repe(e, u) for(int ehead[u]; e; enxt[e])
//
// int read() {// int t0, f1; char c;// while(!isdigit(cgetchar())) fc^45;// while(isdigit(c)) t(t1)(t3)(c^48), cgetchar();// return f? t: -t;
// }
//
// const int N1e510, inf1e9;
//
// int n, k;
// ll ans;
//
// struct BIT {// #define lb(x) ((x)-(x))// static const int X3e5;// int c[X10], tik[X10], tim;// inline void modify(int x, int v1) {// for(; xX; xlb(x)) if(tik[x]tim) c[x]v; else tik[x]tim, c[x]v;// }// inline int query(int x, int v0) {// for(; x; x^lb(x)) if(tik[x]tim) vc[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(px1, px1siz, 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() {// xread(), rread(), fread();// lex-r, rixr;// px[siz]x, px[siz]le, px[siz]ri;// }// inline void reset() {// xfind(x), lefind(le), rifind(ri);// }
// }st[N];
// bool cmpr(state a, state b) {// if(a.rb.r) return a.fb.f||a.fb.fa.xb.x;// return a.rb.r;
// }
// bool cmpf(state a, state b) {// return a.fb.f;
// }
//
// void sol(int le, int ri) {// if(leri) return;// int midleri1;// sol(le, mid), sol(mid1, ri), tre.clear();// sort(stle, stmid1, cmpf), sort(stmid1, stri1, cmpf);// int pi_dnle, pi_uple, pjmid1;// while(pjri) {// while(st[pj].f-st[pi_dn].fkpi_dnmid) tre.modify(st[pi_dn].x, -1);// while(st[pi_up].f-st[pj].fkpi_upmid) tre.modify(st[pi_up].x);// anstre.query(st[pj].ri)-tre.query(st[pj].le-1), pj;// }
// }
//
// int main() {// nread(), kread();// repf(i, n) st[i].get();// sort(px1, px1siz), sizunique(px1, px1siz)-px-1;// repf(i, n) st[i].reset();// sort(st1, st1n, cmpr);// sol(1, n);// printf(%lld, ans);
// }
