算法提高之最大數
-
核心思想：線段樹
- 添加數
- 看作原本的數組有數(0) 現在將他修改成另一個值
- 詢問后l個數的最大值
- query函數具體實現
- 添加數
-
#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 200010;typedef long long LL;int m,p;struct edge{int l,r;int v; //最大值}tr[N*4];void pushup(int u){//兩子樹的最大值的最大值tr[u].v = max(tr[u<<1].v,tr[u<<1 | 1].v);}void build(int u,int l,int r){tr[u] = {l,r};if(l == r) return; //如果是葉子節點int mid = l + r >> 1;build(u<<1,l,mid) , build(u<<1|1,mid+1,r);}int query(int u,int l,int r){//如果子樹節點被區間全覆蓋 說明子樹節點足夠小if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;//子樹節點不夠小 需要細分int mid = tr[u].l + tr[u].r >> 1;int v=0;//如果l在左側 取左子樹if(l<=mid) v = query(u<<1,l,r);if(r>mid) v = max(v,query(u<<1|1,l,r));return v;}void modify(int u,int x,int v){//找到x的位置if(tr[u].l == x && tr[u].r == x) tr[u].v = v;else{int mid = tr[u].l + tr[u].r >> 1;//如果x較小 取左子樹if(x <= mid) modify(u<<1,x,v);else modify(u<<1|1,x,v);//更新修改完后 要向上返回更新父節點值pushup(u);}}int main(){cin>>m>>p;int n=0,last=0;build(1,1,m);while(m--){char op[2];int t;cin>>op>>t;if(op[0] == 'A'){//改最后的數modify(1,n+1,((LL)last + t) % p);n ++;}else{//尋味n-t+1 - n這t個數的最大值last = query(1,n-t+1,n);cout<<last<<endl;}}}
)
