四元组

标签：弹掉 int bkt 四元组 端点 --

 

 

#include<bits/stdc++.h>
using namespace std;
const int N=5e3+10;
int n,a[N]={0},bkt[N+N]={0};
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);//输入 
    for(int i=1;i<=n;i++)//初始化 
        for(int j=i-1;j>=1;j--)
            bkt[a[i]+a[j]]++;
    long long ans=0;//防止爆int 
    for(int i=n;i>=1;i--)//枚举逐渐变小的右端点 
    {
        for(int j=i-1;j>=1;j--) bkt[a[i]+a[j]]--;//右端点为i枚举左端点j把这些弹掉，因为右端点在减少，更新状态，维护bkt数组。 
        //更新数组bkt,因为他是局部性数组一旦i变了他就得把右端点为i的弹掉，因为i减少了一相当于去除了一部分再bkt右端点为i的值 。 
        // 分段统计答案是因为只有这个时候能统计，到最后都是0 
        for(int j=i+1;j<=n;j++) ans+=bkt[a[i]+a[j]];//分段统计答案 
    }
    cout<<ans<<endl;//输出答案 
    return 0;
}

 

 

 

 

 

标签：弹掉,int,bkt,四元组,端点,--
From： https://www.cnblogs.com/wjk53233/p/16905720.html