SCAU2020暑假组队训练 #1_i. sorting colored array

三个小时把能写的写完了2333

A： Array’s Hash

Vasya has invented a new hash function of an array. It is calculated as follows. While the array has at least two elements, the first two elements, call them a1 and a2, are deleted, and the new element a2−a1 is inserted to the beginning of the array. When the array has only one element, this number is a value of Vasya’s hash function of this array.

Vasya has the array a1, a2,…, an. He performs q operations of the following form: “increase all elements in the segment [lj,rj] by vj”. After each operation he wants to know the value of Vasya’s hash function of this array.
Input
The first line contains an integer n (1≤n≤500000) — the size of the array.

The second line contains n integers ai (−109≤ai≤109) — the elements of the array.

The third line contains an integer q (1≤q≤200000) — the number of operations.

Each of the next q lines contains three integers lj, rj, vj (1≤lj≤rj≤n, −109≤vj≤109) — the parameters of the j-th operation.

Output
Output q lines. In the j-th line output one integer — the value of Vasya’s hash function after the j-th operation.

Example
Input
7
4 2 -5 10 4 -2 6
4
2 4 -8
5 7 2
3 3 -1
3 7 3
Output
7
9
8
11

A：题解

队友A的，水题。
树状数组，分奇数位和偶数位来存。
代码如下：

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include <queue>
#include<sstream>
#include <stack>
#include <set>
#include <bitset>
#include<vector>
#define FAST ios::sync_with_stdio(false)
#define abs(a) ((a)>=0?(a):-(a))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define rep(i,a,n) for(int i=a;i<=n;++i)
#define per(i,n,a) for(int i=n;i>=a;--i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
const int maxn = 5e5+200;
const int inf=0x3f3f3f3f;
const double eps = 1e-7;
const double pi=acos(-1.0);
const int mod = 1e9+7;
inline int lowbit(int x){
   return x&(-x);}
ll gcd(ll a,ll b){
   return b?gcd(b,a%b):a;}
void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y){
   if(!b){
   d=a,x=1,y=0;}else{
   ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}}//x=(x%(b/d)+(b/d))%(b/d);
inline ll qpow(ll a,ll b,ll MOD=mod){
   ll res=1;a%=MOD;while(b>0){
   if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
inline ll inv(ll x,ll p){
   return qpow(x,p-2,p);}
inline ll Jos(ll n,ll k,ll s=1){
   ll res=0;rep(i,1,n+1) res=(res+k)%i;return (res+s)%n;}
inline ll read(){
    ll f = 1; ll x = 0;char ch = getchar();while(ch>'9'|ch<'0') {
   if(ch=='-') f=-1; ch = getchar();}while(ch>='0'&&ch<='9') x = (x<<3) + (x<<1) + ch - '0',  ch = getchar();return x*f; }
int dir[4][2] = {
    {
   1,0}, {
   -1,0},{
   0,1},{
   0,-1} };

ll c[maxn];
ll a[maxn];
ll d1[maxn];
ll c1[maxn];
ll d2[maxn];
ll sum3[maxn];
ll sum4[maxn];
ll sum1[maxn];
ll sum2[maxn];



//这里开始是有区间修改的版本，用d表示前后项差，d的前i项和即是a[i]，这样可以实现对d修改后，区间【L,R】内的元素也得到改变
void add_odd(ll pos, ll y, ll n)            //在pos位置+y，对d
{
   
        for(ll i=pos;i<=n;i+=lowbit(i))
        sum1[i] += y, sum2[i] += pos*y; //从这个位置开始，包含pos项的sum都改变。    sum1是d[i]的前缀和，sum2是d[i]*i的前缀和，sum1*pos-sum2就是a的前缀和
}

void add_range_odd(ll l, ll r,ll x, ll n)
{
   
     add_odd(l,x,n), add_odd(r+1,-x,n);
}

ll ask_odd(ll p, ll n)
{
   
        ll ans  = 0;
        for(ll i=p;i>=1;i-=lowbit(i))
        ans += ((p+1)*sum1[i] - sum2[i]);
        return ans;
}

void add_even(ll pos, ll y, ll n)            //在pos位置+y，对d
{
   
        for(ll i=pos;i<=n;i+=lowbit(i))
        sum3[i] += y, sum4[i] += pos*y; //从这个位置开始，包含pos项的sum都改变。    sum1是d[i]的前缀和，sum2是d[i]*i的前缀和，sum1*pos-sum2就是a的前缀和
}

void add_range_even(ll l, ll r,ll x, ll n)
{
   
     add_even(l,x,n), add_even(r+1,-x,n);
}

ll ask_even(ll p, ll n)
{
   
        ll ans  = 0;
        for(ll i=p;i>=1;i-=lowbit(i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111