【BZOJ3745】Norma [分治]

Norma

Time Limit: 20 Sec Memory Limit: 64 MB
[Submit][Status][Discuss]

Description

Input

　　第1行，一个整数N；

　　第2~n+1行，每行一个整数表示序列a。

Output

　　输出答案对10^9取模后的结果。

Sample Input

　　4
　　2
　　4
　　1
　　4

Sample Output

　　109

HINT

　　N <= 500000
　　1 <= a_i <= 10^8

Solution

 1 egin {align}
 2 &基本思路，考虑分治，统计对于左端点在[L,mid]，右端点在[mid+1，R]的区间贡献：\
 3 \
 4 &枚举在[L, mid]中的点i，[mid+1,R]中的点a、b，\
 5 &保证min[i,mid]≤min[mid+1,a]\
 6 &并且max[i,mid]≥max[mid+1,b] \
 7 &然后[mid+1,R]就被分成了三部分：[mid+1,a],[a+1,b],[b+1,R]，(假设a<b)，\
 8 \
 9 &我们考虑分别对三个部分计算贡献：(max=max[i,mid], min=min[i,mid])\
10 &①.[mid+1,a]:Ans=max*min*sum_{j=mid+1}^{a}(j-i+1) \
11 &②.[a+1,b]:Ans=max*sum_{j=a+1}^{b}(min[a+1,j]*(j-i+1)) \
12 &③.[b+1,R]:Ans=sum_{j=b+1}^{R}( max[b+1,j]*min[b+1,j]*(j-i+1)) \
13 \
14 &这时候，显然①可求了。我们继续推导(把(j-i+1)拆开)，显然有：\
15 &②=max*sum_{j=a+1}^{b}min[a+1,j]*j-max*sum_{j=a+1}^{b}min[a+1,j]*(i-1)\
16 &③=sum_{j=b+1}^{R}max[b+1,j]*min[b+1,j]*j-sum_{j=b+1}^{R}max[b+1,j]*min[b+1,j]*(i-1)\
17 \
18 &显然此时②中的sum_{j=a+1}^{b}min[a+1,j]*j、sum_{j=a+1}^{b}min[a+1,j]是可以O(len)预处理的，\
19 &③中的sum_{j=b+1}^{R}max[b+1,j]*min[b+1,j]*j、sum_{j=b+1}^{R}max[b+1,j]*min[b+1,j]也可以O(len)预处理。\
20 \
21 &显然，若b<a类似。所以我们分治一下即可。\
22 \
23 &::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::——BearChild
24 
25 end {align}

BZOJ3745.md

Code

  1 #include<iostream>
  2 #include<string>
  3 #include<algorithm>
  4 #include<cstdio>
  5 #include<cstring>
  6 #include<cstdlib>
  7 #include<cmath>
  8 using namespace std;
  9 typedef long long s64;
 10 
 11 const int ONE = 1000005;
 12 const int MOD = 1e9;
 13 const int INF = 2147483640;
 14 
 15 int get()
 16 {
 17         int res = 1, Q = 1; char c;
 18         while( (c = getchar()) < 48 || c > 57)
 19             if(c == '-') Q = -1;
 20         if(Q) res = c - 48;
 21         while( (c = getchar()) >= 48 && c <= 57)
 22             res = res * 10 + c - 48;
 23         return res * Q;
 24 }
 25 
 26 
 27 int n;
 28 int val[ONE];
 29 int Ans;
 30 
 31 void Modit(int &a)
 32 {
 33         if(a < 0) a += MOD;
 34         if(a >= MOD) a -= MOD;
 35 }
 36 
 37 struct power
 38 {
 39         int Min, MinI;
 40         int Max, MaxI;
 41         int MinMax, MinMaxI;
 42 
 43         friend power operator -(power a, power b)
 44         {
 45             power c;
 46             Modit(c.Min = a.Min - b.Min),
 47             Modit(c.MinI = a.MinI - b.MinI),
 48             Modit(c.Max = a.Max - b.Max),
 49             Modit(c.MaxI = a.MaxI - b.MaxI),
 50             Modit(c.MinMax = a.MinMax - b.MinMax),
 51             Modit(c.MinMaxI = a.MinMaxI - b.MinMaxI);
 52             return c;
 53         }
 54 }A[ONE];
 55 
 56 
 57 int Sum(int a, int b)
 58 {
 59         return (s64)(a + b) * (b - a + 1) / 2 % MOD;
 60 }
 61 
 62 void Solve(int L, int R)
 63 {
 64         if(L == R)
 65         {
 66             Modit(Ans += (s64)val[L] * val[R] % MOD * 1);
 67             return;
 68         }
 69 
 70         int mid = L + R >> 1;
 71 
 72         int minn = INF, maxx = -INF;
 73         A[mid] = (power){0, 0, 0, 0, 0, 0};
 74 
 75         for(int j = mid + 1; j <= R; j++)
 76         {
 77             minn = min(minn, val[j]), maxx = max(maxx, val[j]),
 78             Modit(A[j].Min = A[j - 1].Min + minn),
 79             Modit(A[j].MinI = A[j - 1].MinI + (s64)minn * j % MOD),
 80             Modit(A[j].Max = A[j - 1].Max + maxx),
 81             Modit(A[j].MaxI = A[j - 1].MaxI + (s64)maxx * j % MOD),
 82             Modit(A[j].MinMax = A[j - 1].MinMax + (s64)minn * maxx % MOD),
 83             Modit(A[j].MinMaxI = A[j - 1].MinMaxI + (s64)minn * maxx % MOD * j % MOD);
 84         }
 85 
 86         minn = INF, maxx = -INF;
 87         int a = mid, b = mid;
 88         power del;
 89 
 90         for(int i = mid; i >= L; i--)
 91         {
 92             minn = min(minn, val[i]), maxx = max(maxx, val[i]);
 93             while(minn <= val[a + 1] && a + 1 <= R) a++;
 94             while(maxx >= val[b + 1] && b + 1 <= R) b++;
 95             if(a <= b)
 96             {
 97                 Modit(Ans += (s64)maxx * minn % MOD * Sum(mid + 1 - i + 1, a - i + 1) % MOD);
 98                 del = A[b] - A[a];
 99                 Modit(Ans += (s64)maxx * del.MinI % MOD - (s64)maxx * del.Min % MOD * (i - 1) % MOD);
100                 del = A[R] - A[b];
101                 Modit(Ans += (s64)del.MinMaxI - (s64)del.MinMax * (i - 1) % MOD);
102             }
103             else
104             {
105                 Modit(Ans += (s64)maxx * minn % MOD * Sum(mid + 1 - i + 1, b - i + 1) % MOD);
106                 del = A[a] - A[b];
107                 Modit(Ans += (s64)minn * del.MaxI % MOD - (s64)minn * del.Max % MOD * (i - 1) % MOD);
108                 del = A[R] - A[a];
109                 Modit(Ans += (s64)del.MinMaxI - (s64)del.MinMax * (i - 1) % MOD);
110             }
111         }
112 
113         Solve(L, mid), Solve(mid + 1, R);
114 
115 }
116 
117 int main()
118 {
119         n = get();
120         for(int i = 1; i <= n; i++)
121             val[i] = get();
122         Solve(1, n);
123         printf("%d", Ans);
124 }

View Code