入门

求 1 ~ n 中长度 >= f 的连续区间的最大和

    rep(i, 1, n) s[i] = s[i - 1] + a[i];

    int _min = INT_MAX, ans = INT_MIN;
    rep(i, f, n){
        _min = min(_min, s[i - f]);
        ans = max(ans, s[i] - _min);
    }
    cout << ans << '\n';

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n, f;
int const N = 1e5 + 10;
db const eps = 1e-5;
db a[N], s[N];

bool check(db mid){
    rep(i, 1, n) s[i] = s[i - 1] + (a[i] - mid);

    db ans = INT_MIN, _min = INT_MAX;
    rep(i, f, n){
        _min = min(_min, s[i - f]);
        ans = max(ans, s[i] - _min);
        if(ans >= 0) return true;
    }
    return false;
}

int main(){
    db l = 1, r = 0;
    cin >> n >> f;
    rep(i, 1, n) cin >> a[i], r = max(r, a[i]);

    while(r - l > eps){
        db mid = (l + r) / 2.0;
        if(check(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(r * 1000) << '\n';

    return 0;
} 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n, m, res;
int const N = 5e3 + 10;
int s[N][N];

int op(int x1, int y1, int x2, int y2){
    return (s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}

int main(){
    cin >> n >> m;
    m = min(m, 5001);
    rep(i, 1, n){
        int x, y, v;
        cin >> x >> y >> v;
        s[++ x][++ y] += v;
    }
    rep(i, 1, 5001) rep(j, 1, 5001)
        s[i][j] += (s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1]);
    rep(i, m, 5001) rep(j, m, 5001)
        res = max(res, op(i - m + 1, j - m + 1, i, j));
    cout << res << '\n';

    return 0;
} 

b[1] = a[1];
b[2] = a[2] - a[1];
b[3] = a[3] - a[2];
......
b[n] = a[n] - a[n - 1]

令 a[1] = a[2] = … = a[n]
即 令 b[2] = b[3] = … = b[n] = 0; b[1] 取值任意
而且 b[1] 取值即为 方案数

差分操作 : b[l] += C, b[r + 1] -= C; // l ~ r 区间 全部加 C;

操作方案数 :
1. l = 1, r = n 操作 : 没有意义
2. l = 1, r <= n - 1 ; b[1] += c, b[r + 1] -= c;
3. r = n, l >= 2; b[2 ~ n - 1] += c, b[n + 1] -= c;
4. l >= 2, r <= n - 1; b[l] += c, b[r + 1] -= c;

2 ~ n - 1
min{p, q} + |p - q| = max{p, q};
|p - q| + 1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n;
int const N = 1e5 + 10;
ll a[N], b[N];

int main(){
    cin >> n;
    rep(i, 1, n) cin >> a[i], b[i] = a[i] - a[i - 1];

    ll p, q;
    p = q = 0;
    rep(i, 2, n){
        if(b[i] > 0) p += b[i];
        else q += (-b[i]);
    }
    cout << max(p, q) << '\n' << abs(p - q) + 1;

    return 0;
} 

#include <bits/stdc++.h>
using namespace std;

#define fs first 
#define sc second
#define rep(i, a, b) for(int i = a;i <= b;i ++)
typedef double db;
typedef long long ll;
typedef pair<ll, ll> pll;

int t;
// n : 等级; m: 坐标，从0开始计数
pll pos(ll n, ll m){
    if(!n) return {0, 0}; // 处理边界
    ll len = 1ll << (n - 1); // 本等级内象限的边长
    ll cnt = 1ll << ((n - 1) << 1); // 本等级象限容量

    pll last = pos(n - 1, m % cnt); // 上一等级的坐标信息
    ll x = last.fs, y = last.sc;

    int z = m / cnt; // 位于第几象限
    // 左上象限顺转 90°（y,-x）沿 y对称（-y,-x）更换原点（-y-len,-x+len）
    if(!z) return {-y - len, -x + len};
    // 右上象限更换原点（x+len,y+len）
    else if(z == 1) return {x + len, y + len};
    // 右下象限更换原点（x+len,y-len）
    else if(z == 2) return {x + len, y - len};
    // 左下象限逆转90°（-y,x）沿y对称（y,x）更换原点（y-len,x-len）
    return {y - len, x - len};
}

int main(){
    cin >> t;
    while(t --){
        ll n, p1, p2;
        cin >> n >> p1 >> p2;
        pll pos1 = pos(n, p1 - 1);
        pll pos2 = pos(n, p2 - 1);

        db delta_x = (db)(pos1.fs - pos2.fs);
        db delta_y = (db)(pos1.sc - pos2.sc);
        cout << fixed << setprecision(0) << (sqrt(delta_x * delta_x + delta_y * delta_y) * 5) << '\n';
    }
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;

#define fs first
#define sc second
#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

ll a, b;
ll const MOD = 9901;
unordered_map<ll, ll> prim;

ll qmi(ll a, ll k);
ll sum(ll p, ll k);
void op(ll x);

ll res = 1;

void solution1(){
    for(auto t : prim){
        ll p = t.fs, k = t.sc * b;
        res = res * sum(p, k + 1) % MOD;
    }
}

void solution2(){
    for(auto t : prim){
        ll p = t.fs, k = t.sc * b;
        if((p - 1) % MOD) res = res * (qmi(p, k + 1) - 1) % MOD * qmi(p - 1, MOD - 2) % MOD;
        else res = res * (k + 1) % MOD;
    }
}

int main(){
    cin >> a >> b;
    op(a);
    solution1();
    // solution2();

    if(!a) cout << 0;
    else cout << (res % MOD + MOD) % MOD << '\n';

    return 0;
} 

ll qmi(ll a, ll k){
    ll res = 1;
    while(k){
        if(k & 1) res = (res * a) % MOD;
        k >>= 1;
        a = (a * a) % MOD;
    }
    return res;
}

// 求 p^0 + p^1 + ... + p^(k - 1)
ll sum(ll p, ll k){
    if(k == 1) return 1LL;
    if(k % 2 == 0) return (qmi(p, k / 2) + 1) * sum(p, k / 2) % MOD;
    return (qmi(p, k - 1) + sum(p, k - 1)) % MOD; 
}

void op(ll x){
    for(ll i = 2;i <= x / i;i ++){
        while(x % i == 0){
            x /= i;
            prim[i] ++;
        }
    }
    if(x > 1) prim[x] ++;
}

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)

int n;
char q[10][10];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void change(int x, int y){
    rep(i, 0, 4){
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a <= 4 && b >= 0 && b <= 4)
            q[a][b] ^= 1;           
    }
}

void solve(){
    int ans = INT_MAX;
    rep(k, 0, (1 << 5) - 1){
        char backup[10][10];
        memcpy(backup, q, sizeof q);
        int res = 0;
        rep(i1, 0, 4) if(k >> i1 & 1) change(0, i1), res ++;
        rep(i2, 0, 3) rep(j2, 0, 4)
            if(q[i2][j2] == '0') change(i2 + 1, j2), res ++;

        bool f = true;
        rep(i3, 0, 4) if(q[4][i3] == '0') f = false;

        if(f) ans = min(ans, res);
        memcpy(q, backup, sizeof backup);
    }

    if(ans <= 6) cout << ans << '\n';
    else cout << "-1\n";
}

void mycin(){
    rep(i, 0, 4) cin >> q[i];
    solve();
}

int main(){
    cin >> n;
    while(n --) mycin();

    return 0;
} 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n;
char q[10][10];

int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void change(int x, int y){
    rep(i, 0, 4){
        int a = x + dx[i], b = y + dy[i];
        if(a >= 0 && a <= 4 && b >= 0 && b <= 4)
            q[a][b] ^= 1;           
    }
}

void op(){
    int ans = INT_MAX;
    rep(k, 0, (1 << 5) - 1){
        char backup[10][10];
        memcpy(backup, q, sizeof q);
        int res = 0;
        rep(i1, 0, 4) if(k >> i1 & 1) change(0, i1), res ++;
        rep(i2, 0, 3) rep(j2, 0, 4)
            if(q[i2][j2] == '0') change(i2 + 1, j2), res ++;

        bool f = true;
        rep(i3, 0, 4) if(q[4][i3] == '0') f = false;

        if(f) ans = min(ans, res);
        memcpy(q, backup, sizeof backup);
    }

    if(ans <= 6) cout << ans << '\n';
    else cout << "-1\n";
}

int main(){
    cin >> n;
    while(n --){
        rep(i, 0, 4) cin >> q[i];
        op();
    }

    return 0;
} 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

ll qadd(ll a, ll b, ll p){
    ll res = 0;
    while(b){
        if(b & 1) res = (res + a) % p;
        b >>= 1;
        a = (a + a) % p;
    }
    return res;
}

int main(){
    ll a, b, p;
    cin >> a >> b >> p;
    cout << qadd(a, b, p);

    return 0;
} 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define rep(i, a, b) for(int i = a;i <= b;i ++)
#define per(i, a, b) for(int i = b;i >= a;i --)
typedef long long ll;
typedef double db;

int n, m;
int const N = 5e5 + 10;
ll a[N];

struct node{
    int l, r;
    ll sum, d;
}tr[N * 4];

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

void pushup(node &u, node &lson, node &rson){
    u.sum = lson.sum + rson.sum;
    u.d = gcd(lson.d, rson.d);
}

void pushup(int u){
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r){
    if(l == r){
        ll b = a[l] - a[l - 1];
        tr[u] = {l, r, b, b};
    }else{
        tr[u] = {l, r};
        int mid = tr[u].l + tr[u].r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u); 
    }
}

void modify(int u, int pos, ll val){
    if(tr[u].l == tr[u].r){
        ll t = tr[u].sum + val;
        tr[u] = {pos, pos, t, t};
    }else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(pos <= mid) modify(u << 1, pos, val);
        else modify(u << 1 | 1, pos, val);
        pushup(u);
    }
}

node query(int u, int l, int r){
    if(tr[u].l >= l &&  tr[u].r <= r) return tr[u];
    int mid = tr[u].l + tr[u].r >> 1;
    if(r <= mid) return query(u << 1, l, r);
    else if(l > mid) return query(u << 1 | 1, l, r);
    else{
        node res;
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        pushup(res, left, right);
        return res;
    } 
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    build(1, 1, n);

    while(m --){
        char ch;
        int l, r;
        ll x;
        cin >> ch >> l >> r;
        if(ch == 'C'){
            cin >> x;
            modify(1, l, x);
            if(r + 1 <= n) modify(1, r + 1, -x);
        }else{
            ll res = query(1, 1, l).sum;
            if(l != r) res = gcd(res, query(1, l + 1, r).d);
            cout << abs(res) << '\n';
        }
    }

    return 0;
}