基础知识

[TOC]

二分

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],k;
int f1(int l,int r){
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]>=k)r=mid;
		else l=mid+1;
	}
	return l;
}
int f2(int l,int r){
	while(l<r){
		int mid=l+r+1>>1;
		if(a[mid]<=k)l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
    int n,q,l1,l2;
    cin>>n>>q;
    for(int i=0;i<n;i++){
    	cin>>a[i];
	}
	while(q--){
		cin>>k;
		l1=f1(0,n-1);
		l2=f2(0,n-1);
		if(a[l1]!=k)cout<<"-1 -1"<<endl;
	}
    return 0;
}

归并排序+逆序对的数量

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
long long a[N],backup[N],ans;
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=l;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            backup[k++]=a[i++];
        }
        else {
            backup[k++]=a[j++];
            ans+=mid-i+1;
        }
    }
    while(i<=mid)backup[k++]=a[i++];
    while(j<=r)backup[k++]=a[j++];
    for(int t=l;t<=r;t++){
        a[t]=backup[t];
    }
    
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    merge_sort(1,n);
    cout<<ans;
    return 0;
}

离散化

int a[N];
vector<pair<int,int>>add,query;
vector<int>alls;
int find(int t){
	int l=0,r=alls.size()-1;
	while(l<r){
		int mid=l+r>>1;
		if(alls[mid]>=t)r=mid; 
		else l=mid+1;
	}
	return r+1;
}
for(int i=0;i<n;i++){
	cin>>x>>c;
    add.push_back({x,c});
    alls.push_back(x);	
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto item:add){
    k=find(item.first);
    a[k]+=item.second;
}

通常原数组中会有重复的元素，一般把相同的元素离散化为相同的数据。方法如下：

创建原数组的副本。
将副本中的值从小到大排序。
将排序好的副本去重。
查找原数组的每一个元素在副本中的位置，位置即为排名，将其作为离散化后的值。数组：

// arr[i] 为初始数组,下标范围为 [1, n]

for (int i = 1; i <= n; ++i)  // step 1
  tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
  arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;

vector:

// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp 是 arr 的一个副本
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

结构体：根据题目要求，有时候会把相同的元素跟据输入顺序离散化为不同的数据。此时再用 std::lower_bound() 函数实现就有些困难了，需要换一种思路：

创建原数组的副本，同时记录每个元素出现的位置。
将副本按值从小到大排序，当值相同时，按出现顺序从小到大排序。
将离散化后的数字放回原数组。

struct Data {
  int idx, val;

  bool operator<(const Data& o) const {
    if (val == o.val)
      return idx < o.idx;  // 当值相同时，先出现的元素离散化后的值更小
    return val < o.val;
  }
} tmp[maxn];  // 也可以使用 std::pair

for (int i = 1; i <= n; ++i) tmp[i] = (Data){i, arr[i]};
std::sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; ++i) arr[tmp[i].idx] = i;

RMQ算法/ST表

离线预处理O(nlogn)

O(1)查询a[l,r]区间的最大/最小值

定义f[i,j]为以第i个数为起点，长度为2^j的一段区间中的最大值

f[i,j] = max(f[i,j-1],f[i+2^(j-1),j-1])

 for(int j = 0;j<M;j++){
        for(int i = 1;i+(1<<j)-1<=n;i++)
            if(!j)f[i][j] = a[i];
            else f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    }


    cin>>m;
    while(m--){
        int l,r;
        cin>>l>>r;
        int len = r-l+1;
        int k = log(len)/log(2);
        cout<< max(f[l][k],f[r-(1<<k)+1][k])<<endl;
    }

滑动窗口

int n,k,hh=0,tt=-1;
cin>>n>>k;
for(int i=0;i<n;i++){
    scanf("%d",&a[i]);
}
for(int i=0;i<n;i++){
    while(tt>=hh&&q[hh]<i-k+1)hh++;
    while(tt>=hh&&a[q[tt]]>=a[i])tt--;
    q[++tt]=i;
    if(i-k+1>=0)printf("%d ",a[q[hh]]);
}

求max(aj-ai)

j>i

ans=0,minv=1<<28;
for(ll i=1;i<=n;++i)
{
    ll x;
    scanf("%lld",&x);
    ans=max(ans,x-minv);
    minv=min(minv,x);
}