题解 P4889 【kls与flag】
Viston
·
·
题解
运用了不用map的方法
即把每个杆子可能落到的位置存进数组
运用sort排序一遍
```
#include<bits/stdc++.h>
using namespace std;
long long a,b,c[200002],d[400002],e=0,i,j,k,l;
int main(){
ios::sync_with_stdio(false);
cin>>a>>b; //O(NlogN),放心用cin
for(i=1;i<=a;i++){
cin>>c[i];e+=2;
d[e-1]=i-c[i];d[e]=i+c[i]; //入数组
}
sort(d+1,d+e+1); //排序
for(i=1;i<=2*a;i++){
if(d[i]!=d[i-1]) //如果不在这个点了
k=0;
else k++,l+=k; //如果在，就加一下
}
cout<<l; //输出最后答案
}
```