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

const int N = 100010;
int w[N],n,m;

struct Node{
    int l,r;
    int maxv;
}tr[N*4];

void build(int u, int l, int r){
    if(l == r) tr[u] = {l,r,w[r]};
    else{
        tr[u] = {l,r};
        int mid = l + r >> 1;
        build(u << 1,l,mid); //递归左叶子
        build(u << 1 | 1, mid + 1, r); //递归处理右叶子
        tr[u].maxv = max(tr[u << 1].maxv, tr[u << 1 | 1].maxv);
    }
}

int query(int u,int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxv;
        int mid = tr[u].l + tr[u].r >> 1;
        int maxv = INT_MIN;
        if(l <= mid) maxv = query(u << 1,l,r);
        if( r > mid ) maxv = max(maxv,query(u << 1 | 1, l, r));
        return maxv;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    build(1, 1, n);

    int l, r;
    while (m -- )
    {
        scanf("%d%d", &l, &r);
        printf("%d\n", query(1, l, r));
    }

    return 0;
}

#include<iostream>
using namespace std;
const int N = 32010;
int f[N], tr[N];
int level[N];

int lowbit(int x){
    return  x & -x;
}

void add(int u ){
    for(int i = u; i < N; i += lowbit(i)) tr[i] ++;    
}

int sum(int x){
    int res = 0;
    for(int i = x; i ;  i  -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    int n;
    cin >> n;
    int m = n;
    while(m--){
        int x,y;
        cin >> x >> y;
        x++;
        level[sum(x)] ++;
        add(x);
    }
    for(int i = 0; i < n; i ++) cout << level[i] << endl; 
    return 0;
}

树状数组两个作用
    1.求动态区间和
    2.修改某个位置上的数，主要是通过加操作
构造树状数组的时候，利用差分的思想，在每个位置上进行插入即可完成初始化
add函数中影响的数组中的元素是long n个
和前缀和比起来具有巨大的优势
求和的时候，利用递归进行处理，从最后往前面加，坐标每次都减去一个lowbit

#include<iostream>
using namespace std;
const int N = 100010;
int f[N], tr[N];

int n,m;

int lowbit(int u){
    return u & -u;
}

void add(int x, int y){
    for(int i = x; i <= n; i += lowbit(i))  tr[i] += y;
}

int quary(int x){
    int res = 0;
    for(int i = x; i ;  i -= lowbit(i)) res += tr[i];
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> f[i];
    for(int i = 1; i <= n; i ++) add(i,f[i]);
    while(m--){
        int k, a, b;
        cin >> k >> a >> b;
        if(k == 1) add(a,b);
        else cout << quary(b) - quary(a-1) << endl;
    }
    return 0;
}

注意一下res可能会溢出，所以用longlong 存储

#include<iostream>
using namespace std;
const int N = 100010;
int a[N],tmp[N];
int n;
long long  res;

void merge_sort(int l, int r){
    if( l >= r) return;
    int mid = l + r >> 1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else{
            tmp[k++] = a[j++];
            res += mid - i + 1;
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for( i = l,j = 0; i <= r; j ++,i ++) a[i] = tmp[j];

}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    merge_sort(0,n-1);
    cout << res << endl;
    return 0;
}

压缩状态，将空闲时间压缩到下一时刻，并且进行批量处理

#include<iostream>
#include<algorithm>

#define x first
#define y second
using namespace std;


const int N = 100010;
typedef pair<int,int> PII;

int n, m, T;
PII order[N];
bool st[N];
int last[N],score[N];

int main(){
    cin >> n >> m >> T;
    for(int i = 0; i < m; i ++) cin >> order[i].x >> order[i].y;
    sort(order,order+m);
    for(int i = 0; i < m;){
        //批量处理一个店铺同一时刻的订单
        int j = i;
        while(j < m && order[i] == order[j]) j ++;
        int t = order[i].x, id = order[i].y, cnt = j - i;
        i = j;
        //处理一下t时刻之前的无订单状态
        score[id] -= t - last[id] - 1;
        if(score[id] < 0 ) score[id] = 0;
        if(score[id] <= 3) st[id] = false;

        //处理t时刻的状态
        score[id] += cnt * 2;
        if(score[id] > 5) st[id] = true;

        //更新一下last
        last[id] = t;
    }

    //处理一下last到T没有订单的情况
    for(int i = 1; i <= n; i ++){
        score[i] -= T - last[i]; //此处不用减1，因为是T+1 - last[id] - 1
        if(score[i] <= 3 ) st[i] = false;
    }

    int res = 0;
    //统计一下所有在优先队列中的队伍
    for(int i = 1; i <= n; i ++){
        if(st[i]) res ++;
    }
    cout << res;
    return 0;
}

#include<iostream>
using namespace std;
int n;

int get_second(int h, int m, int s){
    return h * 3600 + m * 60 + s;
}

int get_time(){
    string line;
    getline(cin,line);
    if(line.back() != ')') line += " (+0)";
    int h1,m1,s1,h2,m2,s2,d;
    sscanf(line.c_str(),"%d:%d:%d %d:%d:%d (+%d)",&h1,&m1,&s1,&h2,&m2,&s2,&d);
    return get_second(h2,m2,s2) - get_second(h1,m1,s1) + d * 24 * 3600;
}

int main(){
    cin >> n;
    string line;
    getline(cin,line);
    while(n --){
        int t = (get_time() + get_time()) / 2;
        int hour = t / 3600, minute = t % 3600 / 60, second = t % 60;
        printf("%02d:%02d:%02d\n",hour,minute,second);
    }
}

模拟题有点恶心。。。。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10;
int year,month,day;
int months[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
string date;
int cnt;
struct fin{
    int year;
    int month;
    int day;
    bool operator < (const fin& t){
        if(year != t.year) return year < t.year;
        else if(month != t.month) return month < t.month;
        else return day < t.day;
    }
}Fin[4];

void print_date(int year,int month,int day){
     cout << year  << '-';
   if(month < 10) cout << '0';
   cout << month << '-';
   if(day < 10) cout << '0';
   cout << day;
   cout << endl;
}
void mdy(){
     for(int i = 0; i < date.size(); i += 3){
        int k = (date[i] - '0') * 10 + date[i+1] - '0';
        if(i == 0) month = k;
        if(i == 3) day = k;
        if(i == 6 && k <  50) year = 2000 + k;
        else year = 1900 + k;
    }
    months[2] = 28;
    if((year % 4 == 0 && year % 100 != 0 )|| year % 400 == 0) months[2] = 29;
    if(day == 0 || month == 0 || day > months[month] || month > 12) return; 
    cnt ++;
    Fin[cnt] = {year,month,day};
}

void dmy(){
     for(int i = 0; i < date.size(); i += 3){
        int k = (date[i] - '0') * 10 + date[i+1] - '0';
        if(i == 0) day = k;
        if(i == 3) month = k;
        if(i == 6 && k <  50) year = 2000 + k;
        else year = 1900 + k;
    }
       months[2] = 28;
    if((year % 4 == 0 && year % 100 != 0 )|| year % 400 == 0) months[2] = 29;
    if(day == 0 || month == 0 || day > months[month] || month > 12) return; 
    cnt ++;
    Fin[cnt] = {year,month,day};
}

void ymd(){
    for(int i = 0; i < date.size(); i += 3){
        int k = (date[i] - '0') * 10 + date[i+1] - '0';
        if(i == 0){
            if(k < 50) year = 2000 + k;
            else year = 1900 + k;
        }
        if(i == 3) month = k;
        if(i == 6) day = k;
    }
        months[2] = 28;
    if((year % 4 == 0 && year % 100 != 0 )|| year % 400 == 0) months[2] = 29;
    if(day == 0 || month == 0 || day > months[month] || month > 12 ) return; 
    cnt++;
    Fin[cnt] = {year,month,day};
}
int main(){
    cin >> date;
    ymd();
    mdy();
    dmy();
    sort(Fin+1,Fin+1+cnt);
    for(int i = 1; i <= cnt; i ++){
        if(Fin[i].year != Fin[i+1].year || Fin[i].month != Fin[i+1].month || Fin[i].day != Fin[i+1].day)
                print_date(Fin[i].year,Fin[i].month,Fin[i].day);
    }
    return 0;
} 

曼哈顿距离：折线距离
阿基米德距离 ： 直线距离
遇到蛇形矩阵还是找规律为上册
但是这也是转换的只要技巧
行 /
列 %

#include<iostream>
using namespace std;
int w,m,n;
int res;

int main(){
    cin >> w >> m >> n;
    m--,n--;
    int x1 = m / w, x2 = n / w;
    int y1 = m % w, y2 = n % w;
    if(x1 % 2 ) y1 = w - 1 - y1;

    if(x2 % 2) y2 = w -1 - y2;

    res = abs(x1-x2) + abs(y1-y2);
    cout << res;
    return 0;
}

#include<iostream>
using namespace std;
const int N = 100010;
int a[N],tmp[N];
int n;

void merger_sort(int l, int r){
    if(l >= r) return;
    int mid = l + r >> 1;
    merger_sort(l,mid);
    merger_sort(mid+1,r);
    int i = l, j =  mid + 1;
    int k = 0;
    while(i <= mid && j <= r){
        if(a[i] < a[j] ) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }
    while(j <= r) tmp[k++] = a[j++];
    while(i <= mid) tmp[k++] = a[i++];
    for(int i = l; i <= r; i ++) a[i] = tmp[i-l];
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    merger_sort(0,n-1);
    for(int i = 0; i < n; i ++) cout << a[i] << ' ' ;
    return 0;
}

用枚举年份来代替枚举一长串，从而降低时间复杂度

#include<iostream>
using namespace std;

int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int day1,day2;
int res;

bool check(int u){
    month[2] = 28;
    int day = u % 100;
    int m = u % 10000 / 100;
    int year = u / 10000;
    if(m > 12 || day > 31) return false;
    if((year % 100 != 0 && year % 4 == 0 ) || year % 400 == 0)
        month[2]++ ;
    if(day > month[m]) return false;

    return true;
}

int main(){
    cin >> day1 >> day2;
    for(int i = 1000; i < 10000; i ++){
        int l = i, r = i;
        while(r) l = l * 10 + r % 10, r /= 10;
        if(l >= day1 && l <= day2 && check(l)) res ++;
    }
    cout << res;
    return 0;
}