P3378 【模板】堆

题目简述

给定三个操作，求数列中最小的数，删除数列中最小的数，插入一个新的数

思路

板子题没什么好说，用 stl 自带的优先队列很好写，但手写的也要掌握。
建议参考这篇博客

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+6;
int tr[N];
int main(){
  int n,len=0;
  cin>>n;
  while(n--){
    int op;
    cin>>op;
    switch(op){
      case 1:{
        int x;
        cin>>x;
        tr[++len]=x;
        int kdl=len;
        while(kdl){
          if(tr[kdl>>1]>tr[kdl])tr[kdl>>1]^=tr[kdl]^=tr[kdl>>1]^=tr[kdl];
          else break;
          kdl>>=1;
        }
        break;
      }
      case 2:{
        cout<<tr[1]<<endl;
        break;
      }
      case 3:{
        int kdl=1;
        tr[len]^=tr[1]^=tr[len]^=tr[1];
        tr[len]=0;
        len--;
        while(kdl<len){
          int ls=(kdl<<1),rs=(kdl<<1|1);
          if(ls>len){
            break;
          }
          if(rs>len){
            if(tr[ls]<tr[kdl])tr[kdl]^=tr[ls]^=tr[kdl]^=tr[ls];
            break;
          }
          if(tr[ls]<tr[rs]){
            if(tr[ls]<tr[kdl])tr[kdl]^=tr[ls]^=tr[kdl]^=tr[ls],kdl=ls;
            else break;
          }
          else {
            if(tr[rs]<tr[kdl])tr[kdl]^=tr[rs]^=tr[kdl]^=tr[rs],kdl=rs;
            else break;
          }
        }
        break;
      }
    }
  }
  return 0;
}

PS:有时候真的很奇怪我是怎么能把代码都写这么冗长的/kk

P3865 【模板】ST 表

题目简述

对于给定的数列，要求以\(\theta(1)\)的时间复杂度计算出\([l_i,r_i]\)中最大值

思路

没什么可讲的，但要注意，计算区间长度的对数要是 log2(r-l+1) 不加1的话大多数情况下没问题，但是当 l=r 的时候会报错
BTW，用scanf printf 不会超时，用cin cout 是会超时的qwq
具体思路可以参考这个博客

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],s[N][25];
int n,m;
void in(int &x){
  x=0;
  int f=1;
  char c=getchar();
  while(c>'9'||c<'0'){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(c>='0'&&c<='9'){
    x=(x<<1)+(x<<3)+c-'0';
    c=getchar();
  }
  x*=f;
}
void pre_work(){
  for(int i=1;(1<<i)<=n&&i<25;i++){
    for(int j=1;j+(1<<i)-1<=n;j++){
      s[j][i]=max(s[j][i-1],s[j+(1<<(i-1))][i-1]);
    }
  }
}
void query(int l,int r){
  int k=log2(r-l+1);
  printf("%d\n",max(s[l][k],s[r-(1<<k)+1][k]));
}

int main(){
  in(n);in(m);
  for(int i=1;i<=n;i++)in(s[i][0]);
  pre_work();
  for(int i=1;i<=m;i++){
    int l,r;
    in(l);in(r);
    query(l,r);
  }
  return 0;
}