P4889 kls与flag_牛客博客

看了题解发现自己想的十分复杂。

现在来说一下不一样的方法。

题目要求放倒后可以重合的竹竿的对数，

自然会想到去研究：两个什么样的竹竿可以重合。

设第 $i$ 个竹竿是的高度为 $l[i]$ ，

那么对于任意的 $1<=i<j<=n$ ，

它们倒地重合有三种情况：

一起倒在中间: $l[i]+l[j]=j-i$ ，这等价于 $l[i]+i=-(l[j]-j)$ 。
一起倒在左边: $l[j]-l[i]=j-i$ ，这等价于 $l[i]-i=l[j]-j$ 。
一起倒在左边: $l[i]-l[j]=j-i$ ，这等价于 $l[i]+i=l[j]+j$ 。

以上等价转化用到了大家在高中学习中做导数题经常用到的构造函数思想。

对于 $2,3$ ，我们可以将 $l[i]+i,l[i]-i$ 存进 $A$ , $B$ 数组，

若有 $k$ 个 $i$ 满足 $l[i]+i$ 或 $l[i]-i$ 相等，

则显然对应着 $k*(k-1)/2$ 对优秀的竹竿。

扫一遍即可算出答案。这里是 $O(n)$ 的。

而对于 $1$ ，我们可以将 $-(l[i]-i)$ 存进 $C$ 数组，

再遍历一遍 $l[i]+i$ 的 $A$ 数组，

对于每个 $i$ ，二分查找 $A[i]$ 在 $C$ 数组中出现的左界与右界 $l,r$

那么就对应了 $r-l+1$ 对优秀的竹竿。

这一过程是 $O(nlogn)$ 。

而对于两个竹竿，最多满足 $1,2,3$ 中的一项，故以上计算不重不漏。

总计时间复杂度是 $O(nlogn)$ 。

#include<algorithm>
#include<iostream>
#include<cstdio>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int maxn=200020;

int n,m,l[maxn],a[maxn],b[maxn];
int worrk1(){
    int Ans=0;
    rep(i,1,n)
    rep(j,i+1,n)
    if(l[i]+l[j]==j-i||l[i]-l[j]==j-i||l[j]-l[i]==j-i)Ans++;
    return Ans;
}
int main(){
    long long Ans=0;
    scanf("%d%d",&n,&m);
    rep(i,1,n){
        scanf("%d",&l[i]);
        a[i]=l[i]+i;
        b[i]=l[i]-i;
    }
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    long long ji=0;a[0]=2000000000;
    rep(i,1,n){
        if(a[i]==a[i-1])ji++;
        else {
            Ans+=ji*(ji-1)/2;
            ji=1;
        }
    }
    Ans+=ji*(ji-1)/2;
    ji=1;

    b[0]=2000000000;
    rep(i,1,n){
        if(b[i]==b[i-1])ji++;
        else {
            Ans+=ji*(ji-1)/2;
            ji=1;
        }
    }
    Ans+=ji*(ji-1)/2;

    rep(i,1,n)b[i]=-b[i];
    sort(b+1,b+n+1);
    //rep(i,1,n)cout<<a[i]<<' '<<b[i]<<endl;
    rep(i,1,n){
        int key=a[i];
        long long ll,rr;
        int l,r,mid;
        l=1,r=n;
        while(l<r){
            mid=(l+r)>>1;
            if(b[mid]<key)l=mid+1;
            else r=mid;
        }
        ll=l;

        l=1,r=n;
        while(l<r){
            mid=(l+r+1)>>1;
            if(b[mid]>key)r=mid-1;
            else l=mid;
        }
        rr=r;

        if(b[ll]==key&&b[rr]==key&&ll<=rr)Ans+=rr-ll+1;
    }
    cout<<Ans;
    return 0;
}