z3475 的博客

题解 P4889 【kls与flag】

容易发现我们可以用一个数组记录flag向左/向右倒下后头部相同坐标的数量,简单点说就是按照桶排序的思路来统计

然后? 对于每一个数按照C(2,n)=n*(n-1)/2,求和即为答案

但是m高达1e9,这个数组绝对会爆,我们需要用数据结构来存储,这里我用的是Treap Splay hash表,熟用stl处理冲突只需5行代码超简单

顺便提一下hash怎么做

vector<pair<int,int>> hash[N]

简单的hash函数-除一个常数M(这样冲突能控制到O(M)时间复杂度

但是向左倒下可能有负数,这样我们+一个表示正负数界线的常数L

考虑N的值,存入最大1e9+2e5,M当然越小越好,这里我取M为5000,N就是(1e9+2e5)/5000*2=400080(正负数要乘2),保险一点N取402000,L就是201000

Tips:其实M还可以更小的

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
template<typename T=int>T gi(){
    register T i(0);register bool f(false);
    register char c=getchar();
    while (!isdigit(c)) f=c=='-'?true:false,c=getchar();
    while (isdigit(c)) i=c-'0'+(i<<3)+(i<<1),c=getchar();
    return f?-i:i;
}
#define N 200010
#define pii pair<int,int>

int n,m;
int a[N];

#define M 5000
#define L 201000
vector<pii> ha[402000];

void add(ri i){
    vector<pii> &v=ha[L+i/M];
    vector<pii>::iterator j=lower_bound(v.begin(),v.end(),pii(i,0));
    if (j!=v.end()&&j->first==i) j->second++;
    else v.insert(j,pii(i,1));
}

int main(){
    n=gi();m=gi();
    for(ri i=0;i!=n;i++){
        ri t=gi();
        add(i+t);add(i-t);
    }
    long long ans=0;
    for (vector<pii> *i=ha;i!=ha+402000;i++)
        for(vector<pii>::iterator j=i->begin();j!=i->end();j++)
            ans+=((ll)j->second*(j->second-1)>>1);
    printf("%lld\n",ans);
}

2018-09-23 18:33:25 in 题解