- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e5+5;
- struct A
- {
- int x;
- double w;
- }maxx[maxn];
- int n,m;
- bool mark[maxn];
- template<class t>void red(t &x)
- {
- int w=1;
- x=0;
- char ch=getchar();
- while(ch>'9'||ch<'0')
- {
- if(ch=='-')
- w=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9')
- {
- x=(x<<3)+(x<<1)+ch-'0';
- ch=getchar();
- }
- x*=w;
- }
- void input()
- {
- freopen("input.txt","r",stdin);
- }
- void update(int l,int r,int z,int x,int y)
- {
- if(l==r&&l==x)
- {
- maxx[z].w=y/x;
- maxx[z].x=x;
- return;
- }
- int j=(l+r)>>1;
- if(x<=j)
- update(l,j,z<<1,x,y);
- else
- update(j+1,r,z<<1|1,x,y);
- if(maxx[z<<1].w<maxx[z<<1|1].w)
- maxx[z]=maxx[z<<1|1];
- else
- maxx[z]=maxx[z<<1];
- }
- int f(int x)
- {
- int ans=0;
- for(int i=1;i<x;++i)
- ans+=mark[i]?0:1;
- return ans;
- }
- int main()
- {
- //input();
- red(n);
- red(m);
- int x,y;
- for(int i=1;i<=m;++i)
- {
- red(x);
- red(y);
- if(y)
- mark[x]=1;
- if(!y&&mark[x])
- mark[x]=0;
- update(1,n,1,x,y);
- printf("%d\n",maxx[1].x-f(maxx[1].x));
- }
- return 0;
- }
没动脑子瞎打 10 分
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=4e5+5;
- struct A
- {
- int s;
- double h;
- }maxx[maxn];
- int n,m;
- template<class t>void red(t &x)
- {
- int w=1;
- x=0;
- char ch=getchar();
- while(ch>'9'||ch<'0')
- {
- if(ch=='-')
- w=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9')
- {
- x=(x<<3)+(x<<1)+ch-'0';
- ch=getchar();
- }
- x*=w;
- }
- void input()
- {
- freopen("input.txt","r",stdin);
- }
- int query(int l,int r,int z,int h)
- {
- if(maxx[z].h<=h)
- return 0;
- if(l==r)
- return maxx[z].h>h;
- int j=(l+r)>>1;
- if(maxx[z<<1].h<=h)
- return query(j+1,r,z<<1|1,h);
- return query(l,j,z<<1,h)+maxx[z].s-maxx[z<<1].s;
- }
- void update(int l,int r,int z,int x,int y)
- {
- if(l==r&&l==x)
- {
- maxx[z].h=(double)y/x;
- maxx[z].s=1;
- return;
- }
- int j=(l+r)>>1;
- if(x<=j)
- update(l,j,z<<1,x,y);
- else
- update(j+1,r,z<<1|1,x,y);
- maxx[z].h=max(maxx[z<<1].h,maxx[z<<1|1].h);
- maxx[z].s=maxx[z<<1].s+query(j+1,r,z<<1|1,maxx[z<<1].h);
- }
- int main()
- {
- input();
- red(n);
- red(m);
- int x,y;
- for(int i=1;i<=m;++i)
- {
- red(x);
- red(y);
- update(1,n,1,x,y);
- printf("%d\n",maxx[1].s);
- }
- return 0;
- }
蜜汁打挂 70 分
query 里忘记改 double 了
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=4e5+5;
- struct A
- {
- int s;
- double h;
- }maxx[maxn];
- int n,m;
- template<class t>void red(t &x)
- {
- int w=1;
- x=0;
- char ch=getchar();
- while(ch>'9'||ch<'0')
- {
- if(ch=='-')
- w=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9')
- {
- x=(x<<3)+(x<<1)+ch-'0';
- ch=getchar();
- }
- x*=w;
- }
- void input()
- {
- freopen("input.txt","r",stdin);
- }
- int query(int l,int r,int z,double h)
- {
- if(l==r)
- return maxx[z].h>h;
- int j=(l+r)>>1;
- if(maxx[z<<1].h<=h)
- return query(j+1,r,z<<1|1,h);
- return query(l,j,z<<1,h)+maxx[z].s-maxx[z<<1].s;
- }
- void update(int l,int r,int z,int x,int y)
- {
- if(l==r&&l==x)
- {
- maxx[z].h=(double)y/x;
- maxx[z].s=1;
- return;
- }
- int j=(l+r)>>1;
- if(x<=j)
- update(l,j,z<<1,x,y);
- else
- update(j+1,r,z<<1|1,x,y);
- maxx[z].h=max(maxx[z<<1].h,maxx[z<<1|1].h);
- maxx[z].s=maxx[z<<1].s+query(j+1,r,z<<1|1,maxx[z<<1].h);
- }
- int main()
- {
- input();
- red(n);
- red(m);
- int x,y;
- for(int i=1;i<=m;++i)
- {
- red(x);
- red(y);
- update(1,n,1,x,y);
- printf("%d\n",maxx[1].s);
- }
- return 0;
- }
100 分
来源: http://www.bubuko.com/infodetail-3090000.html