推歌：无理无智/徵羽摩柯 by 阿良良木健
来自我们物理老师推荐的初中物理题：一个不知道是啥东西的东西在斜着的传送带向上面传送，然后已知其摩擦系数(本来是未知的但是能算就已知了)和重力，且本物体做匀速直线运动，问在什么条件下其收到的摩擦力是向下的，什么时候不受摩擦力，什么时候摩擦力向上并且求此时物体的动能(里头的条件具体数值全忘光了
还是复习性质的闲话
-
单调栈
就是满足单调性质的栈,当插入一个新的数时不断判断是否比目前栈顶的数要(大/小)，若(大/小)则插入，否则不断进行pop操作直到满足条件
//STL自带的栈 for(int i=n;i>=1;i--){ while(!sta.empty()&&sta.top()<=a[i]) sta.pop(); ans[i]=(sta.empty())?(0):(sta.top()); sta.push(a[i]); }//数组模拟 for(int i=n;i>=1;i--){ while(top!=0&&sta[top]<=a[i]) top--; ans[i]=sta[top]; sta[++top]=h[i]; } -
单调队列
和单调栈区别不太大
for(int i=1;i<k;++i){ while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back(); q.push_back(i); } for(int i=k;i<=n;++i){ while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back(); q.push_back(i); while(q.front()<=i-k) q.pop_front(); printf("%lld ",a[q.front()]); } -
线段树
参见昨天的闲话附带的学习笔记，复杂度 \(\text O(n \log n)\)
-
分块
大段维护，小段朴素，复杂度 \(\text O(n \sqrt n)\)
块长通常是\(\sqrt n\)，具体是多少最合适就直接去造数据跑哪个快但是我觉得喵喵不知道哪里找的出题人不会去出 YNOI 毒瘤卡常题
点击查看代码
#include<bits/stdc++.h> using namespace std; inline int read(){ int s=0,w=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } const int N=5e5+10,SN=1000,inf=1<<30; int T,n,a[N]; class Block{ public: int sqn,ka[N]; class BLOCK{ public: int val,l,r; }bl[SN]; inline void init(int n){ sqn=sqrt(n); for(int i=1;i<=sqn;i++){ bl[i].l=bl[i-1].r+1; bl[i].r=(i==sqn)?n:bl[i].l+sqn; bl[i].val=0; for(int j=bl[i].l;j<=bl[i].r;j++){ ka[j]=i; bl[i].val+=a[j]; } } } inline void Update(int l,int r,int v){ while(bl[ka[l]].l!=l&&l<=r){ a[l]+=v; ++l; } while(l+sqn-1<=r){ for(int i=l;i<=l+sqn-1;i++) a[i]+=v; bl[ka[l]].val+=v*sqn; l+=sqn; } while(l<=r){ a[l]+=v; ++l; } } inline int Query(int l,int r){ int sum=0; while(bl[ka[l]].l!=l&&l<=r){ sum+=a[l]; ++l; } while(l+sqn-1<=r){ sum+=bl[ka[l]].val; l+=sqn; } while(l<=r){ sum+=a[l]; ++l; } return sum; } }bl; signed main(){ int n=read(); for(int i=1;i<=n;i++) a[i]=read(); bl.init(n); for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read(); if(opt==0)bl.Update(l,r,c); else cout<<bl.Query(r,r)<<endl; } } -
莫队
优雅的暴力，把操作离线后进行排序，但是我觉得不考
点击查看代码
int n,m,k,sqrtn,a[1000001],ans[1000001]; class Mobius{ public: int sum,bl[1000001]; class block{ public: int l,r,id,k; inline void Join(int li,int ri,int i){ l=li,r=ri, id=i,k=(li-1)/sqrtn+1; return; } inline bool operator<(block p){ if(k!=p.k)return l<p.l; if(k&1)return r<p.r; return r>p.r; } }blo[100001]; inline void Join(int l,int r,int i){ blo[i].Join(l,r,i); return; } inline void Add(int i){ sum-=bl[i]*bl[i], ++bl[i], sum+=bl[i]*bl[i]; } inline void Del(int i){ sum-=bl[i]*bl[i], --bl[i], sum+=bl[i]*bl[i]; } inline void Solve(){ sort(blo+1,blo+m+1); int l=1,r=0; for(int i=1;i<=m;++i){ while(l>blo[i].l) Add(a[--l]); while(r<blo[i].r) Add(a[++r]); while(l<blo[i].l) Del(a[l++]); while(r>blo[i].r) Del(a[r--]); ans[blo[i].id]=sum; } } }bl; signed main(){ n=read(),m=read(),k=read(); sqrtn=sqrt(n); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=m;++i){ int l=read(),r=read(); bl.Join(l,r,i); } bl.Solve(); for(int i=1;i<=m;i++){ cout<<ans[i]<<endl; } } -
平衡树
我认为 splay 相较其他而言比较简单，不过代码较长
点击查看代码
#include<bits/stdc++.h> using namespace std; #define int long long const int N=100005,INF=0X66CCFF0712; int t,opt; class Spaly{ private: int f[N],ch[N][2],cnt[N],siz[N],sz,root; public: int key[N]; inline void clear(int x){ ch[x][0]=ch[x][1]=f[x]=cnt[x]=key[x]=siz[x]=0; } inline int get(int x){ return ch[f[x]][1]==x; } inline void update(int x){ if(x){ siz[x]=cnt[x]; if(ch[x][0]){ siz[x]+=siz[ch[x][0]]; } if(ch[x][1]){ siz[x]+=siz[ch[x][1]]; } } } inline void rotate(int x){ int old=f[x],oldf=f[old],which=get(x); ch[old][which]=ch[x][which^1]; f[ch[old][which]]=old; ch[x][which^1]=old; f[old]=x;f[x]=oldf; if(oldf) ch[oldf][ch[oldf][1]==old]=x; update(old); update(x); return; } inline void splay(int x){ for(int fa;fa=f[x];rotate(x)) if(f[fa]) rotate(get(x)==get(fa)? fa : x); root=x; } inline void insert(int v){ if(root==0){ ++sz; root=sz; ch[root][0]=ch[root][1]=f[root]=0; key[root]=v; cnt[root]=siz[root]=1; return; } int cur=root,fa=0; while(1){ if(key[cur]==v){ ++cnt[cur]; update(cur); update(fa); splay(cur); break; } fa=cur; cur=ch[cur][key[cur]<v]; if(cur==0){ ++sz; ch[sz][0]=ch[sz][1]=0; key[sz]=v; siz[sz]=1; cnt[sz]=1; f[sz]=fa; ch[fa][key[fa]<v]=sz; update(fa); splay(sz); break; } } } inline int find(int v){ int ans=0,cur=root; while(1){ if(v<key[cur]) cur=ch[cur][0]; else { ans+=(ch[cur][0] ? siz[ch[cur][0]] : 0); if(v==key[cur]){ splay(cur); return ans+1; } ans+=cnt[cur]; cur=ch[cur][1]; } } } inline int findth(int k){ int cur=root; while(1){ if(ch[cur][0] && k<=siz[ch[cur][0]]) cur=ch[cur][0]; else { int tem=(ch[cur][0] ? siz[ch[cur][0]] : 0) +cnt[cur]; if(k<=tem) return key[cur]; k-=tem; cur=ch[cur][1]; } } } inline int pre(){ int cur=ch[root][0]; while(ch[cur][1]) cur=ch[cur][1]; return cur; } inline int nxt(){ int cur=ch[root][1]; while(ch[cur][0]) cur=ch[cur][0]; return cur; } inline void del(int v){ find(v); if(cnt[root]>1){ --cnt[root]; update(root); return; } if(!ch[root][0] && !ch[root][1]){ clear(root); root=0; sz=0; return; } if(!ch[root][0]){ int oldroot=root; root=ch[root][1]; f[root]=0; clear(oldroot); --sz; return; } else if(!ch[root][1]){ int oldroot=root; root=ch[root][0]; f[root]=0; clear(oldroot); --sz; return; } int lpre=pre(),oldroot=root; splay(lpre); f[ch[oldroot][1]]=root; ch[root][1]=ch[oldroot][1]; update(root); return; } }TrEE; signed main(){ // freopen("1.in","r",stdin); cin>>t; TrEE.insert(INF); TrEE.insert(-INF); while(t--){ int x,opt; cin>>opt; if(opt==1){ cin>>x; TrEE.insert(x); } else if(opt==2){ cin>>x; TrEE.del(x); } else if(opt==3){ cin>>x; TrEE.insert(x); cout<<TrEE.find(x)-1<<endl; TrEE.del(x); } else if(opt==4){ cin>>x; cout<<TrEE.findth(x+1)<<endl; } else if(opt==5){ cin>>x; TrEE.insert(x); cout<<TrEE.key[TrEE.pre()]<<endl; TrEE.del(x); } else if(opt==6){ cin>>x; TrEE.insert(x); cout<<TrEE.key[TrEE.nxt()]<<endl; TrEE.del(x); } } }相较而言，这种时候pb_ds或许是更好的选择？
-
珂朵莉树
骗分利器？但是我不会
