# 區間和、最大值、最小值問題
---
# binary indexed tree 二叉樹
[https://zerojudge.tw/ShowProblem?problemid=f315](https://) -Apcs第4題

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

long long ans = 0;
long long bit[SIZE];
int n;
int R[SIZE];
int L[SIZE];

int sum(int pos) {
    int s = 0;
    while(pos > 0) {
        s += bit[pos];
        pos -= pos & (-pos);
    }
    return s;
}

void add(int pos) {
    while(pos <= 2*n) {
        bit[pos] += 1;
        pos += pos & (-pos);
    }
}

int main () {
    cin >> n;
    for(int i = 1; i <= 2*n; i++) {
        int tmp;
        cin >> tmp;
        if(L[tmp] == 0) {
            L[tmp] = i;
        } else {
            R[tmp] = i;
        }
    }
    for(int i = 1; i <= n; i++) {
        ans += sum(R[i]) - sum(L[i]); /// sum
        add(R[i]);  add(L[i]); ///  setup binary tree
    }
    cout << ans;
}

## 1. 求左右兩邊大於中間的數
## 2. 從一開始，邊建表邊算ans

---
# segment tree 線段數
[https://zerojudge.tw/ShowProblem?problemid=d799](https://)
---

#include <bits/stdc++.h>
using namespace std;
#define AC ios_base::sync_with_stdio(0);  cin.tie(0);  cout.tie(0);
#define SIZE 1000005

int n;
int num[SIZE];
struct aka{
    long long sum;
    long long lazy;
}tree[SIZE];

int Lc(int n) {return n*2;}
int Rc(int n) {return n*2+1;}

void build(int x, int y, int k) {
    if (x == y) {
         tree[k].sum = num[x];
         tree[k].lazy = 0;
         return;
    }
    int m = (x+y)/2;
    build(x,m,Lc(k));
    build(m+1,y,Rc(k));
    tree[k].lazy = 0;
    tree[k].sum = tree[Lc(k)].sum + tree[Rc(k)].sum;
}

/**position  room  value**/
void update(int x, int y, int a, int b, int k, int val) {
    /**need to be updated**/
    if (tree[k].lazy != 0) {
        tree[k].sum += tree[k].lazy*(y-x+1);
        if (x != y) {
            tree[Rc(k)].lazy += tree[k].lazy;
            tree[Lc(k)].lazy += tree[k].lazy;
        }
        tree[k].lazy = 0;
    }
    if (x > b || y < a) return;
    if (x >= a && y <= b) {
        /**in the range change the sum then mark the child node**/
        tree[k].sum += val*(y-x+1);
        if (x != y) {
            tree[Lc(k)].lazy += val;
            tree[Rc(k)].lazy += val;
        }
        /**had been written**/
        return;
    }
    int m = (x+y)/2;
    update( x ,m,a,b,Lc(k),val);
    update(m+1,y,a,b,Rc(k),val);
    /**important!! the node need to be update at the end**/
    tree[k].sum = tree[Lc(k)].sum + tree[Rc(k)].sum;
}

long long query(int x, int y, int a, int b, int k) {
    if (tree[k].lazy != 0) {
        tree[k].sum += tree[k].lazy*(y-x+1);
        if (x != y) { /*propagation*/
            tree[Lc(k)].lazy += tree[k].lazy;
            tree[Rc(k)].lazy += tree[k].lazy;
        }
        /*init*/
        tree[k].lazy = 0;
    }
    if (x > b || y < a || x > y) return 0;
    /**return the sum**/
    if (x >= a && y <= b) return tree[k].sum;
    /**else go recursive**/
    int m = (x+y)/2;
    return query(x,m,a,b,Lc(k)) + query(m+1,y,a,b,Rc(k));
}

int main () {
    AC
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    build(1,n,1);
    int m;
    cin >> m;
    while (m--) {
        int tmp, x, y, s;
        cin >> tmp;
        if (tmp == 1) {
            cin >> x >> y >> s;
            update(1,n,x,y,1,s);
            /*
            for (int i = n-1+x; i <= n-1+y; i++) cout << tree[i].lazy << " ";
            cout << endl;
            */
        } else if (tmp == 2) {
            cin >> x >> y;
            cout << query(1,n,x,y,1) << endl;
        }
    }

}

# 區間最小值 apcs zj g277 3.幸運數字

#include <bits/stdc++.h>
using namespace std;
#define AC ios_base::sync_with_stdio(0); cout.tie(0);
#define SIZE 300000

struct T{
    int minn;
    int m_pos;
};

T s[SIZE<<2], small = {INT_MAX,0};
int num[SIZE], n;
long long pre[SIZE];

void build(int L, int R, int k) {
    if(L == R) {
        s[k] = {num[L],L};
        return;
    }
    int m = (L+R)>>1;
    build(L,m,(k<<1));
    build(m+1,R,(k<<1)+1);
    s[k].minn = min(s[(k<<1)].minn,s[(k<<1)+1].minn);
    if(s[(k<<1)].minn < s[(k<<1)+1].minn) s[k].m_pos = s[(k<<1)].m_pos;
    else s[k].m_pos = s[(k<<1)+1].m_pos;
}


void find_small(int x, int y,int left, int right, int k) {

    if(x >= left && y <= right) {
        if(small.minn > s[k].minn) small = s[k];
        return;
    }
    if(x > right || left > y) return;
    int m = (x+y)>>1;
    if(m >= right) return find_small(x,m,left,right,(k<<1));
    else if(m < left) return find_small(m+1,y,left,right,(k<<1)+1);
    else {
        find_small(x,m,left,right,(k<<1));
        find_small(m+1,y,left,right,(k<<1)+1);
    }
}

int main() {
    AC
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> num[i];
        pre[i] = pre[i-1]+num[i];
    }
    build(1,n,1);
    int left = 1, right = n;
    while(left < right) {
        small = {INT_MAX,0};
        find_small(1,n,left,right,1);
        long long sL = pre[small.m_pos-1]-pre[left-1];
        long long sR = pre[right] - pre[small.m_pos];
        if(sR >= sL) left = small.m_pos+1;
        else right = small.m_pos-1;

    }
    cout << num[left] << endl;
}