点击打开链接
每次更新 判断名次即:最值编号是否改变 如果改变,则记录改变的时间
#include <iostream> #include <algorithm> #include <cstdio> #include <cmath> #include <cstring> using namespace std; const int M=1e5+20; struct Seg{ long long score; int num; }seg[M*4];//节点保存最大值和对应编号 void pushup(int rt) { seg[rt].score=seg[rt<<1].score; seg[rt].num=seg[rt<<1].num;// if(seg[rt].score<seg[rt<<1|1].score)//相等时 编号小的优先 { seg[rt].score=seg[rt<<1|1].score; seg[rt].num=seg[rt<<1|1].num; } } void build(int l,int r,int rt) { if(l==r) { seg[rt].score=0;// seg[rt].num=l; return; } int m=(l+r)>>1; build(l,m,rt<<1); build(m+1,r,rt<<1|1); pushup(rt); } void update(int p,int x,int l,int r,int rt) { if(l==r) { seg[rt].score+=x; return; } int m=(l+r)>>1; if(p<=m)//更新p所在的那段区间 { update(p,x,l,m,rt<<1); } else { update(p,x,m+1,r,rt<<1|1); } pushup(rt); } int main() { int t; cin>>t; while(t--) { int flag=0,pos=1,time;//pos要初始化为1阿！！得分都为0时1最大 int n,q; scanf("%d%d",&n,&q); build(1,n,1);// for(int i=1;i<=q;i++) { int x,p; scanf("%d%d",&p,&x); update(p,x,1,n,1); // cout<<"@"<<seg[1].num<<endl; if(seg[1].num!=pos)//每次更新后 看winner是否改变 { pos=seg[1].num; flag++; time=i; } } if(flag) cout<<time<<endl; else cout<<0<<endl; } return 0; }
更简单的做法：
#include<bits/stdc++.h> #define P(x,y) make_pair(x,y) using namespace std; const int MX = (1<<17) , MOD = 1e9+7; struct ev{ int team , points; ev(){} ev(int id , int P):team(id) , points(P){} }; bool operator < (const ev&A , const ev&B){ if(A.points != B.points) return A.points < B.points; else return A.team > B.team; } int cur[MX]; int main(){ int T , n , Q; scanf("%d",&T); while(T--){ scanf("%d %d",&n,&Q); set < ev > S; for(int j=1;j<=n;j++){ cur[j] = 0; S.insert(ev(j , 0)); } int winner = 1 , ans = 0; for(int j=1;j<=Q;j++){ int who , d; scanf("%d %d",&who,&d); S.erase(ev(who , cur[who])); cur[who] += d; S.insert(ev(who , cur[who])); auto tt = --S.end(); //cout<<tt->team<<endl; if(tt->team != winner) ans = j; winner = tt->team; } cout<<ans<<endl; } }
