AtCoder Beginner Contest 368（ABC368）
Count Arithmetic Subarrays题意：
判断有多少个区间是等差数列（不能重排）。
\(1 \le n \times 10^5\)。
思绪：
赛时看错题了，以为这个区间可以重排，卡了 8min，小丑了。
首先容易注意到，对于一个区间 \(\)，若其是等差数列，则这个区间的子区间 \(\) 肯定也是子序列，造成的贡献是 \(\frac{(r-l+1)(r-l+2)}{2}\)。
那么考虑求出所有极长等差区间，设 \(d_i = a_{i+1} - a_i\)，若 \(i\) 能参加 \(i-1\) 的等差区间，当且仅当 \(d_i = d_{i-1}\)；否则就要新开一个等差子区间。
注意末了答案要加 \(n-1\)。
时间复杂度为 \(O(N)\)。
完整代码： #include#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(A) memset(A,0,sizeof(A))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);#define For(i,l,r) for(int i=l;i=l;i--)using namespace std;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const int N=2e5+6;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c
页:
[1]