Luogu P4889 kls与flag

思路

思路总是从暴力开始

• 暴力做法30分

  两两枚举

  条件是:

  两杆的高度的和或者差等于两杆的坐标距离

• 70分

  由数据范围可以猜测 $O(logN)$

  设第 $i$ 根杆的高度为 $h_i$

  每根杆子可以向左向右倒

  向左倒尖端坐标 $i-h_i$

  向右倒尖端坐标 $i+h_i$

  也就是说在某个坐标如果有两根能倒到这里

  就满足条件

  如果有多个点(设有 $k$ 个)能倒到这里

  那么就两两组合,共 $\frac{ (1+k) \times k}{2}$ 种

• 100分

  还是在70分的基础上

  发现数据范围太大了

  不如离散化

  记录每根杆能倒到的坐标

  共有 $2n$ 个

  排序后,就能轻易找到相同坐标点上的杆子个数

代码

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int Maxn = 2e5+7;

int n, m, tot;
long long ans, a[Maxn<<1];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1, x; i <= n; ++i)
    {
        scanf("%d", &x);
        a[++tot] = i-x;
        a[++tot] = i+x;
    }
    sort(a+1, a+1+tot);
    int cur = 1, cnt = 0;
    while(cur <= tot)
    {
        cnt = 0;
        while(cur+1 <= tot && a[cur+1] == a[cur])
        {
            ++cur;
            ++cnt;
        }
        ans += 1ll*cnt*(cnt+1)/2;
        ++cur;
    }
    printf("%lld\n", ans);
    return 0;
}