题解 P4889 【kls与flag】

容易发现我们可以用一个数组记录flag向左/向右倒下后头部相同坐标的数量，简单点说就是按照桶排序的思路来统计 然后? 对于每一个数按照C(2,n)=n*(n-1)/2,求和即为答案 但是m高达1e9,这个数组绝对会爆,我们需要用数据结构来存储,这里我用的是~~Treap~~ ~~Splay~~ hash表,熟用stl处理冲突只需5行代码超简单 顺便提一下hash怎么做 ```cpp 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还可以更小的 ```cpp #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); } ```