每日打卡 11 18 #632 div2 C. Eugene and an array

没想到竟然是个 1700的题！！！

原题链接

题意

一个区间中若有一段连续的子区间的区间和为0，则这个区间是 不好的 ，给定一个区间求这个区间内有多少 好 的子区间

输入

第一行是数组a大小为n，n小于等于2e5
第二行n个数，代表a[i].  1e-9<=a[i]<=1e9;

输出

输出好的子区间个数

分析一下:

先分析一下怎么去判断一段区间的和0，如果直接相加求和是肯定会t；需要用前缀和优化，

然后进行判断如果sum[i]==sum[j]的话则从i+1到 j 这段区间和就为0；

根据题意一个好的区间其中任何一个子区间的和是不能为0的；

那么我们可以使用双指针 ， 定义两个指针 l , r；

令l=1，r=1;从头开始遍历前缀和数组并将每一个元素标记，

如果当前个元素都与之前都不同则以这个位置为结尾且开头不能比   l  小的所有子区间都是好的

故 ans+=r-l+1;

如果出现相同的则将  l   指针移动到 该位置+2的位置可以自行画图理解一下，然后在进行

ans+=r-l+1;

如果出现0的话那么就行特判一下；

最后一遍遍历就可以得到答案；

代码如下

/*  E.M.T!!!!!   */
#include<iostream>
#include<map>
using namespace std;
const int N=2e5+6;
long long A[N],sum[N];
map<long long,long long>flag;
int main(){
   long long n,l,r,i,k;long long ans=0;
   scanf("%lld",&n);
   for(i=1;i<=n;i++){
   scanf("%lld",&A[i]);	
   sum[i]=sum[i-1]+A[i];	
   } 
   for(l=1,r=1;r<=n;r++){
   if(flag[sum[r]]!=0){
   k=l;//如果出现一个为0的区间中还包含着一个为0的区间那么我们的 r 会更晚到达大的区间的末尾故 l指针移动会往前走，所以我们要避免这种情况； 
   l=flag[sum[r]]+2;
   if(l<k)l=k;
   }
   if(sum[r]==0&&flag[sum[r]]==0&&l==1){
   	l=2;                         //关于0的特判; 
   }
   flag[sum[r]]=r;	
   ans+=r-l+1;
   }	
  printf("%lld",ans);
 return 0;	
}  

其实这道双指针的题确实有难度困扰我好几个星期了，得益于某次关于求子区间个数问题的，才有了这次的思路.............. 

虽然是1700的题但还能做，不要被所谓的难度吓住，要自己去试试才知道行不行。

明天就是周赛了。。。希望可以打好点吧，AK不太可能希望能做出点有含金量.的题.

据说明天有Re:0的题.......哈哈哈哈哈哈哈哈哈

我的E.M.T wwwwwww

我好兴奋啊！！！！！！！！！！！！！！！！！！！！！！！！