这道题还不错….我太蠢了 想不来QAQ 膜了一下线段树做法之后发现还有简单粗暴的分块算法 好劲啊 线段树做法比较巧妙 推荐去看看黄学长的 有个细节要注意 取右边的贡献时要用区间贡献减去左边的贡献 因为右边的贡献在算的时候并没有被左边约束 ORZ HZWER 然后是分块 块内维护一个单调上升序列 跟普通的不一样 意会一下就懂了 每次就直接块内重新构造序列 每个块依次二分求值 Po姐那里会告诉你怎样分块更快。。 ORZ PoPoQQQ 这道题线段树的速度快一点。。 线段树
#include<bits/stdc++.h> using namespace std; const int N=400005; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int c[N];double mx[N]; int query(double k,int x,int l,int r) { int mid=(l+r)>>1,lc=x<<1,rc=lc|1; if(l==r)return k<mx[x]; if(mx[lc]<=k)return query(k,rc,mid+1,r); return c[x]-c[lc]+query(k,lc,l,mid); } void change(double k,int u,int x,int l,int r) { int mid=(l+r)>>1,lc=x<<1,rc=lc|1; if(l==r){c[x]=1,mx[x]=k; return;} if(u<=mid)change(k,u,lc,l,mid); else change(k,u,rc,mid+1,r); mx[x]=max(mx[lc],mx[rc]); c[x]=c[lc]+query(mx[lc],rc,mid+1,r); } int main() { int n=read(),m=read(); double x,y; while(m--) { x=read(),y=read(); change(y/x,(int)x,1,1,n); printf("%d\n",c[1]); } return 0; }分块
#include<bits/stdc++.h> using namespace std; const int N=100010; const double eps=1e-10; inline int read() { char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f; } int bl[N]; double a[N]; struct node{ double s[1010]; int l,r,tot; void bulid() { int i; double u=0; tot=0; for(i=l;i<=r;i++) if(a[i]>u+eps) u=a[i],s[++tot]=a[i]; } int query(double &x) { int r=tot+1-(upper_bound(s+1,s+1+tot,x+eps)-s); if(r)x=s[tot]; return r; } }e[120]; int main() { int n=read(),m=read(),b,i,j,x,y; b=sqrt(n*log(n)/log(2)/2.0); for(i=1;(i-1)*b+1<=n;i++) e[i].l=(i-1)*b+1,e[i].r=min(i*b,n); for(i=1;i<=n;i++) bl[i]=(i-1)/b+1; while(m--) { x=read(),y=read(); a[x]=(double)y/x; e[bl[x]].bulid(); double u=0; int ans=0; for(j=1;e[j].l;j++)ans+=e[j].query(u); printf("%d\n",ans); } return 0; }