平面最近点对
经典的分治问题，把所有的点按照 \(x\) 排序，然后分治处理两个子区间，然后枚举离中心少于已知最小值的点，判断能否出现更小值。
int n,temp[250000];
struct node{
int x,y;
}a[500500];
bool cmp(node l,node r){
if(l.x==r.x)return l.y<r.y;
return l.x<r.x;
}
double dis(int l,int r){
return sqrt((a[l].x-a[r].x)*(a[l].x-a[r].x)+(a[l].y-a[r].y)*(a[l].y-a[r].y));
}
bool cmp2(int x,int y){
return a[x].y<a[y].y;
}
double merge(int l,int r){
double d;
if(l==r){return 1e9;}
if(l==r-1){
return dis(l,r);
}
int mid=(l+r)>>1;
double d1=merge(l,mid);
double d2=merge(mid+1,r);
d=min(d1,d2);
int k=0;
for(int i=l;i<=r;i++){
if(fabs(a[mid].x-a[i].x)<d)
temp[k++]=i;
}
sort(temp,temp+k,cmp2);
for(int i=0;i<k;i++){
for(int j = i + 1;j<k&&a[temp[j]].y-a[temp[i]].y<d;j++){
double d3=dis(temp[i],temp[j]);
if(d > d3)d=d3;
}
}
return d;
}
signed main() {
n=read();
for(int i=1;i<=n;i++){
a[i].x=read();
a[i].y=read();
}
sort(a+1,a+1+n,cmp);
double k=merge(1,n);
printf("%.4lf",k);
return 0;
}
Blue Marry开公司
几乎是一道李超线段树的板子题。
int n;
struct line{
f96 k,b;
}p[N];
int cnt;
int s[N<<2];
inline f96 clac(int id,int x){
return p[id].k*(x-1)+p[id].b;
}
inline int cmp(f96 x,f96 y) {
if(x-y>eps)return 1;
if(y-x>eps)return -1;
return 0;
}
inline void change(int k,int l,int r,int p){
int &q=s[k],mid=(l+r)>>1;
int bmid=cmp(clac(p,mid),clac(q,mid));
if(bmid==1||(!bmid&&p<q))swap(p,q);
int bl=cmp(clac(p,l),clac(q,l)),br=cmp(clac(p,r),clac(q,r));
if(bl==1||(!bl&&p<q))change(lc,l,mid,p);
if(br==1||(!br&&p<q))change(rc,mid+1,r,p);
}
inline void insert(int k,int l,int r,int ql,int qr,int id){
if(l>=ql&&r<=qr){
change(k,l,r,id);
return;
}
int mid=(l+r)>>1;
if(l>=mid)insert(lc,l,mid,ql,qr,id);
if(mid<r)insert(rc,mid+1,r,ql,qr,id);
}
inline int ask(int k,int l,int r,int p){
if(l==r)return clac(s[k],p);
int mid=(l+r)>>1,res=clac(s[k],p);
if(mid>=p)res=max(res,ask(lc,l,mid,p));
if(mid<p)res=max(res,ask(rc,mid+1,r,p));
return res;
}
signed main(){
n=read();
char op[50];
f96 b,k;
int x;
up(i,1,n){
scanf("%s",op+1);
if(op[1]=='P'){
scanf("%Lf %Lf",&b,&k);
cnt++;
p[cnt].b=b;p[cnt].k=k;
insert(1,1,1e5+100,1,1e5+100,cnt);
}
else{
x=read();
cout<<ask(1,1,1e5+100,x)/100<<endl;;
}
}
return 0;
}
Rmq mex
看起来就非常莫队是吧。
然而，如何快速找出 \(mex\) 呢？
如果直接加一位一位的查找，复杂度肯定会炸。
有两种解决办法：
-
对着值域建一棵线段树，然后上二分。
-
对值域分块。
int n,m;
int a[N],block;
int pos[N];
int ans[N];
struct node{
int l,r,id;
}q[N];
inline bool cmp(node x,node y){
if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
if(pos[x.l]&1)return x.r>y.r;
return x.r<y.r;
}
int K=500;
int cnt[N],num[N];
inline void add(int x){
if(!cnt[x])num[x/K]++;
cnt[x]++;
}
inline void del(int x){
if(cnt[x]==1)num[x/K]--;
cnt[x]--;
}
inline void ask(int x){
for(int i=1;i<=K;i++){
if(num[i-1]!=K){
for(int j=(i-1)*K;j<i*K;j++){
if(!cnt[j]){
ans[q[x].id]=j;
return;
}
}
}
}
}
signed main(){
n=read();m=read();
block=sqrt(n);
up(i,1,n){
a[i]=read();
pos[i]=(i-1)/block+1;
}
up(i,1,m){
q[i].l=read();
q[i].r=read();
q[i].id=i;
}
sort(q+1,q+1+m,cmp);
int l=q[1].l,r=q[1].r;
for(int i=l;i<=r;i++)add(a[i]);
ask(1);
up(i,2,m){
while(l<q[i].l)del(a[l++]);
while(l>q[i].l)add(a[--l]);
while(r<q[i].r)add(a[++r]);
while(r>q[i].r)del(a[r--]);
ask(i);
}
up(i,1,m)cout<<ans[i]<<endl;
return 0;
}
楼房重建
很有意思的一道题，题意简化一下就是求最长上升斜率。
既然是单调递增，那么我们线段树的每一个节点可以维护这个节点所对应的区间的最大值，与从这段区间开头可以看到的区间内的所有楼房。
那么问题来了，该如何进行 \(push\_up\) 操作。
显然合并区间的所有楼房一定可以看到左边的区间第一个位置看到的所有楼房（这应该很显然吧）
我们可以先查找右区间的左区间的最大值，如果这个最大值比左区间的最大值小，那么有区间的左区间的所有答案一定看不到，所以我们就可以递归查找右区间的右区间
如果右区间的左区间的最大值比左区间的最大值大，那么原来被右区间的左区间挡住的现在一样会被挡住，我们就可以加上右区间的答案，所以我们可以递归查找右区间的左区间
代码非常短。
int n,m,ans[N<<2];
db maxl[N<<2];
inline int ask(int k,int l,int r,db maxx){
if(maxl[k]<=maxx)return 0;
if(l==r)return maxl[k]>maxx;
int mid=(l+r)>>1;
if(maxl[lc]<=maxx)return ask(rc,mid+1,r,maxx);
return ask(lc,l,mid,maxx)+ans[k]-ans[lc];
}
inline void change(int k,int l,int r,int pos,db v){
if(l==r){
ans[k]=1;
maxl[k]=v;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)change(lc,l,mid,pos,v);
else change(rc,mid+1,r,pos,v);
maxl[k]=max(maxl[lc],maxl[rc]);
ans[k]=ans[lc]+ask(rc,mid+1,r,maxl[lc]);
}
signed main(){
n=read(),m=read();
int l,r;
up(i,1,m){
l=read(),r=read();
change(1,1,n,l,(db)r/l);
cout<<ans[1]<<endl;
}
return 0;
}
CPU监控
查询历史版本最大。
刚刚开始时，有一个非常 \(native\) 的想法，直接考虑把所有的 \(\max\) 取最大就行了。
如果这样，你只能得 \(20\)分。
为什么？
因为有 \(push\_down\)，会改变你下传的值，也就是你的答案会因为没有及时下传而改变。
那么该如何解决这个问题呢？
想象一下，你给每个点开一个队列，把所有的标记按照顺序存在这个队列里，然后标记下传的时候就把父亲节点的队列传给儿子节点，然后答案就是儿子节点的前缀最大值。
但是这样肯定是会炸的。
我们发现，对于一个点，首次赋值操作之后的任何修改都可以看作赋值操作。
于是操作序列化简为（重点）：加操作+赋值操作。
struct SegmentTree{
struct node{
int l,r;
int ans,hisans;
int add,agn;
int maxadd,maxagn;
bool vis;
}tr[N<<2];
inline void push_up(int k){
tr[k].ans=max(tr[lc].ans,tr[rc].ans);
tr[k].hisans=max(tr[lc].hisans,tr[rc].hisans);
}
inline void build(int k,int l,int r){
tr[k].l=l;tr[k].r=r;
if(l==r){
tr[k].ans=tr[k].hisans=a[l];
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(k);
}
inline void doadd(int k,int val,int max_val){
if(tr[k].vis){
tr[k].maxagn=max(tr[k].maxagn,tr[k].agn+max_val);
tr[k].hisans=max(tr[k].hisans,tr[k].ans+max_val);
tr[k].ans+=val;
tr[k].agn+=val;
}
else{
tr[k].maxadd=max(tr[k].maxadd,tr[k].add+max_val);
tr[k].hisans=max(tr[k].hisans,tr[k].ans+max_val);
tr[k].ans+=val;
tr[k].add+=val;
}
}
inline void doagn(int k,int val,int max_val){
if(tr[k].vis){
tr[k].hisans=max(tr[k].hisans,max_val);
tr[k].maxagn=max(tr[k].maxagn,max_val);
}
else{
tr[k].vis=1;
tr[k].maxagn=max_val;
tr[k].hisans=max(tr[k].hisans,max_val);
}
tr[k].ans=tr[k].agn=val;
}
inline void push_down(int k){
doadd(lc,tr[k].add,tr[k].maxadd);
doadd(rc,tr[k].add,tr[k].maxadd);
tr[k].add=tr[k].maxadd=0;
if(tr[k].vis){
doagn(lc,tr[k].agn,tr[k].maxagn);
doagn(rc,tr[k].agn,tr[k].maxagn);
tr[k].vis=0;
tr[k].agn=tr[k].maxagn=0;
}
}
inline int ask(int k,int l,int r){
if(tr[k].l>=l&&tr[k].r<=r)return tr[k].ans;
int mid=(tr[k].l+tr[k].r)>>1,res=-inf;
push_down(k);
if(mid>=l)res=max(res,ask(lc,l,r));
if(mid<r)res=max(res,ask(rc,l,r));
return res;
}
inline int askhis(int k,int l,int r){
if(tr[k].l>=l&&tr[k].r<=r)return tr[k].hisans;
int mid=(tr[k].l+tr[k].r)>>1,res=-inf;
push_down(k);
if(mid>=l)res=max(res,askhis(lc,l,r));
if(mid<r)res=max(res,askhis(rc,l,r));
return res;
}
inline void add(int k,int l,int r,int val){
if(tr[k].l>=l&&tr[k].r<=r){
doadd(k,val,val);
return;
}
int mid=(tr[k].l+tr[k].r)>>1;
push_down(k);
if(mid>=l)add(lc,l,r,val);
if(mid<r)add(rc,l,r,val);
push_up(k);
}
inline void assign(int k,int l,int r,int val){
if(tr[k].l>=l&&tr[k].r<=r){
doagn(k,val,val);
return;
}
int mid=(tr[k].l+tr[k].r)>>1;
push_down(k);
if(mid>=l)assign(lc,l,r,val);
if(mid<r)assign(rc,l,r,val);
push_up(k);
}
}T;
signed main(){
n=read();
up(i,1,n)a[i]=read();
T.build(1,1,n);
m=read();
char op[3];
int l,r,z;
while(m--){
scanf("%s",op+1);
if(op[1]=='A'){
l=read();r=read();
write(T.askhis(1,l,r),1);
}
if(op[1]=='Q'){
l=read();r=read();
write(T.ask(1,l,r),1);
}
if(op[1]=='P'){
l=read();r=read();z=read();
T.add(1,l,r,z);
}
if(op[1]=='C'){
l=read();r=read();z=read();
T.assign(1,l,r,z);
}
}
return 0;
}
CF718C
这道题其实是很考验对矩阵的基本理解。
矩阵满足交换律，结合律。
所以可以线段树直接硬上。
int n,m;
int a[N];
struct mat{
int a[3][3];
mat(){
memset(a,0,sizeof a);
}
friend mat operator+(mat a,mat b){
mat c;
up(i,1,2) {
up(j,1,2){
c.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
}
}
return c;
}
inline mat operator*(const mat&rhs)const{
mat c;
up(i,1,2){
up(k,1,2){
up(j,1,2){
c.a[i][j]=(c.a[i][j]+a[i][k]*rhs.a[k][j])%mod;
}
}
}
return c;
}
inline bool empty(){
if(a[1][1]!=1) return 0;
if(a[1][2]!=0) return 0;
if(a[2][1]!=0) return 0;
if(a[2][2]!=1) return 0;
return 1;
}
inline void clear(){
memset(a,0,sizeof a);
a[1][1]=1;a[2][2]=1;
}
};
mat ksm(mat a,int b){
mat ret;
ret.clear();
while(b){
if(b&1) ret=ret*a;
a=a*a;
b>>=1;
}
return ret;
}
mat base,fir;
struct SegmentTree{
struct node{
int l,r;
mat sum,tag;
}tr[N<<2];
inline void push_up(int k){
tr[k].sum=tr[lc].sum+tr[rc].sum;
}
inline void build(int k,int l,int r){
tr[k].l=l;tr[k].r=r;
tr[k].tag.clear();
if(l==r){
tr[k].sum=fir*ksm(base,a[l]-1);
return;
}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
push_up(k);
}
inline void push_down(int k){
if(!tr[k].tag.empty()){
tr[lc].sum=tr[lc].sum*tr[k].tag;
tr[rc].sum=tr[rc].sum*tr[k].tag;
tr[lc].tag=tr[lc].tag*tr[k].tag;
tr[rc].tag=tr[rc].tag*tr[k].tag;
tr[k].tag.clear();
}
}
inline void add(int k,int l,int r,mat val){
if(tr[k].l>=l&&tr[k].r<=r){
tr[k].tag=tr[k].tag*val;
tr[k].sum=tr[k].sum*val;
return;
}
int mid=(tr[k].l+tr[k].r)>>1;
push_down(k);
if(mid>=l)add(lc,l,r,val);
if(mid<r)add(rc,l,r,val);
push_up(k);
}
inline mat ask(int k,int l,int r){
if(tr[k].l>=l&&tr[k].r<=r)return tr[k].sum;
int mid=(tr[k].l+tr[k].r)>>1;
mat x;
push_down(k);
if(mid>=l)x=x+ask(lc,l,r);
if(mid<r)x=x+ask(rc,l,r);
return x;
}
}T;
signed main(){
base.a[1][1]=1;base.a[1][2]=1;
base.a[2][1]=1;base.a[2][2]=0;
fir.a[1][1]=1;fir.a[1][2]=1;
n=read();m=read();
up(i,1,n)a[i]=read();
int op,l,r,x;
T.build(1,1,n);
while(m--){
op=read();
if(op==1){
l=read();r=read();x=read();
T.add(1,l,r,ksm(base,x));
}
else{
l=read();r=read();
write(T.ask(1,l,r).a[1][2]%mod,1);
}
}
return 0;
}