ACM
构造
1016字
ACM
树
构造
1094字
C 思维 & 树 C* Namomo 2C 区间减1，代价为长度的平方，问将区间操作为全0的最小代价和最大代价。
cpp 1#include <iostream> 2 3#include <algorithm> 4#include <string> 5#include <vector> 6#include <stack> 7#include <queue> 8#include <set> 9#include <map> 10#include <unordered_map> 11#include <unordered_set> 12#include <random> 13#include <chrono> 14 15#include <cstdio> 16#include <cstring> 17#include <cmath> 18#include <ctime> 19#include <cstdlib> 20#include <cassert> 21 22#define itn int 23#define fro for 24#define scnaf scanf 25#define sacnf scanf 26#define Fastin freopen("in.txt", "r", stdin) 27#define Fastout freopen("out.txt", "w", stdout) 28#define manx maxn 29#define lowbit(x) ((x) & (-x)) 30#define ceil(n, p) (((n) +(p) - 1) / (p)) 31#define DBG(x) (void)(cout << "L" << __LINE__ << ": " << #x << " = " <<( x) << '\n') 32#define clr(a, x) memset((a), x, sizeof (a)) 33#define min(a, b) ((a) < (b)? (a): (b)) 34#define max(a, b) ((a) > (b)? (a): (b)) 35 36using namespace std; 37typedef long long ll; 38 39int read(){ 40 int ng=0,x=0; 41 char ch=getchar(); 42 for(;ch<'0' || ch>'9';ch=getchar()) ng|=ch=='-'; 43 for(;ch>='0' && ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0'; 44 return ng?-x:x; 45} 46/*------------------------------------------------------------------------------------*/ 47ll gcd(ll x, ll y){return !x? y: gcd(y % x, x);} 48void exgcd(ll a, ll b, ll &x, ll &y){ 49 if(!b){x = 1; y = 0;return;} 50 exgcd(b, a % b, y, x); y -= a / b * x; 51} 52ll qp(ll a, ll p){ 53 if(p < 0) return 0; 54 ll ans = 1; while(p){if(p & 1) ans = ans * a ; a = a * a; p >>= 1;} 55 return ans; 56} 57ll qp(ll a, ll p, ll M){ 58 ll ans = 1; while(p){ if(p & 1) ans = ans * a % M; a = a * a % M; p >>= 1;} 59 return ans; 60} 61/*------------------------------------------------------------------------------------*/ 62 63const int maxn = 5e5 + 10; 64const int M = 1e9 + 7; 65int a[maxn], b[maxn]; 66 67ll cal(int l, int r){return (r - l) * 1ll * (r - l) % M;} 68 69stack<pair<int, int>> sta; 70 71int main(){ 72// Fastin; 73 int n; scnaf("%d", &n); 74 for(int i = 1; i <= n; i++) scanf("%d", a + i); a[n + 1] = 0; 75 76 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1]; 77 while(b[n + 1] == 0) n--; 78 ll ans = 0; 79 int p = 1, q = 1; while(b[q] >= 0) q++; 80 while(p <= n + 1){ 81 if(b[p] + b[q] > 0){ 82 ans += -b[q] * cal(p, q); ans %= M; 83 b[p] += b[q]; 84 q++; while(q <= n + 1 && b[q] >= 0) q++; 85 } 86 else if(b[p] + b[q] == 0){ 87 ans += b[p] * cal(p, q); ans %= M; 88 p++; q++; while(p <= n + 1 && b[p] < 0) p++; while(q <= n + 1 && b[q] >= 0) q++; 89 } 90 else{ 91 ans += b[p] * cal(p, q); ans %= M; 92 b[q] += b[p]; 93 p++; while(p <= n + 1 && b[p] < 0) p++; 94 95 } 96 } 97 printf("%lld ", ans % M); 98 99 for(int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i - 1]; 100 ans = 0; 101 for(int i = 1; i <= n + 1; i++){ 102 if(b[i] > 0) sta.push({i, b[i]}); 103 else if(b[i] < 0){ 104 while(1){ 105 pair<int, int> now = sta.top(); sta.pop(); 106 if(now.second + b[i] < 0){ 107 ans += now.second * cal(now.first, i); ans %= M; 108 b[i] += now.second; 109 } 110 else{ 111 ans += -b[i] * cal(now.first, i); ans %= M; 112 now.second += b[i]; 113 sta.push(now); 114 break; 115 } 116 117 } 118 } 119 } 120 121 printf("%lld\n", ans); 122 123 return 0; 124} I 构造 虽然感觉还是说不太清楚qaq
...