尬笑...现场又没做出来，明知道是找出递推规律，最后想不出来，然后 暴力异或模拟TLE了。
最后队友想出来一个很秒的方法...
看上面这个沙雕图....
要计算所有对 正数区间有贡献的
(1) 首先是粗红色横线： 对于连续的正数而言，每次正整数的区间如横线对应的方式 计算增加 （倒着往前）,所以如果某位置 数为正数 则 positive(连续正数)++
(2)然后是细红色线划掉部分：我们去掉被花掉的部分所剩下的新的序列部分即是（偶数个负—>正）的区间，所以计算剩余长度仍然是按照(1)中连续性质规则。
但是怎么记录和找到之前区间的个数。而且对于每一次出现的负数，我们要求其前面所对应的所有 符合（2）中条件个数。
而解决这一问题就使用 swap（）。由于每一次出现负数，会导致从该点开始前面对应的区间段 正负号发生变化（即记录长度没变，但是连续区间正负号变了），而我们又是按照（1）的方法去递推求个数的。
所以每次出现 负数，就导致前面计算 连续正数的跑到计算负数区间的贡献里面去了，而正数区间个数则是由前面负数区间个数得到的 （负负为正）。
所以，就是一个 区间贡献问题
#include <bits/stdc++.h> #define ll long long using namespace std; int main(){ int n,tmp; scanf("%d",&n); ll a=0,b=0;//a记录正数区间个数，b记录负数区间个数 ll pos=0,neg=0;//开long long 不然会爆 for(int i=0;i<n;i++){ scanf("%lld",&tmp); if(tmp>0) pos++; else{ swap(pos,neg); neg++; } a += pos; b += neg; } printf("%lld %lld\n",b,a); }
转载于:https://www.cnblogs.com/Tianwell/p/11530761.html
