CF961E Tufurama 题解
二维数点做法
题意
给定长度为 (n) 的序列 (a),统计二元组 ((i,j)) 的个数,使得该二元组满足 (1 leq i 。(n) 在 (2 times 10^{5}) 级别,(a_i) 在 (1 times 10^{9}) 级别。
思路分析
我们考虑把序列中 (n) 个元素看成 ((i,a_i)) 坐标的点,至于平面直角坐标系中。我们先忽略“(1 leq i ”的条件。可以发现,对于某一个 (i),我们要统计的是所有的 (j) 中满足 (j leq a_i, a_j geq i) 的点的个数,也就是横坐标小于等于当前点、纵坐标大于等于当前点的点的个数。画出图就是下面的样子:
至于具体怎么处理数点过程,我们按照先横坐标再纵坐标的方式对于点排序。然后我们可以把每个询问 ((a_i,i)) 做排序,代表查询横坐标小于等于 (a_i),纵坐标大于等于 (i) 的点的个数。我们横坐标从小到大一列一列地统计点(即一根扫描线在 x 轴上从小往大扫),用树状数组维护纵坐标上离散化过后的每个位置的已统计点的点数前缀和,统计纵坐标大于等于 (i) 的区间内的点数,就可以知道对应的答案了。
那么我们怎么处理 (1 leq i 的条件呢?首先我们考虑在的统计中,出现的 (i = j) 的情况,可以发现,如果这样的情况被统计到了,(代入条件可得)就会满足 (a_i geq i, a_i geq i),于是我们直接在序列上遍历统计 (a_i geq i) 的个数,在总统计答案中减掉就行。
然后就是 (i 的条件如何处理,我们发现 (a_i geq j, a_j geq i) 和 (a_j geq i, a_i geq j)(即交换 (i,j) 后)是等效的,也就是说每一个满足条件的点对被统计了两遍。于是我们在刚刚的基础上,把统计答案除以二,就得到了正确结果。
代码
#include
using namespace std;
typedef long long LL;
const int N = 5e5 + 5;
const int M = 5e5 + 5;
int n,m;
int a[N];
int ycnt;
int qcnt;
int yrk[N];
struct quest
{
int x,y;
}que[N*2];
int ans[N];
bool cmp1(quest xx,quest yy)
{
return xx.x = 1;i -= lowbit(i))
ans += t[i];
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
LL samecnt = 0;
for(int i = 1;i > a[i];
if(a[i] >= i)
samecnt++;
yrk[i] = a[i];
que[++qcnt] = {a[i],i};
}
sort(que+1,que+1+n,cmp1);
sort(yrk+1,yrk+1+n);
ycnt = unique(yrk+1,yrk+1+n)-1-yrk;
int idx = 1;
LL ans = 0;
for(int i = 1;i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net