O(nlogn)线段树上二分被卡常求助
查看原帖
O(nlogn)线段树上二分被卡常求助
146492
xuchenhao2008楼主2023/11/10 22:15

60pts

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
int Q,type[maxn]={},t[maxn]={},x[maxn]={},y[maxn]={},s[maxn]={},itag[maxn<<2]={},ftag[maxn<<2]={},tot = 0;
struct node{
    int v,p;
    bool operator+=(int bst){
        v+=bst;
    }
};
bool operator<(node a,node b){
    if(a.v!=b.v)return a.v<b.v;
    else return a.p<b.p;
}
bool operator>(node a,node b){
    if(a.v!=b.v)return a.v>b.v;
    else return a.p>b.p;
}
bool operator<=(node a,node b){
    return a.v<=b.v;
}
bool operator>=(node a,node b){
    return a.v>=b.v;
}
node ibig[maxn<<2]={},ismall[maxn<<2]={},fbig[maxn<<2]={},fsmall[maxn<<2]={};

#define POS(x) (lower_bound(s+1,s+1+tot,x)-s)
multiset<int> I,F;
inline int lc(int &p){
    return p<<1;
}
inline int rc(int &p){
    return p<<1|1;
}
inline void pushdown(int &p){
    ibig[lc(p)] += itag[p], ismall[lc(p)] += itag[p], itag[lc(p)] += itag[p];
    ibig[rc(p)] += itag[p], ismall[rc(p)] += itag[p], itag[rc(p)] += itag[p];
    itag[p] = 0;
    fbig[lc(p)] += ftag[p], fsmall[lc(p)] += ftag[p], ftag[lc(p)] += ftag[p];
    fbig[rc(p)] += ftag[p], fsmall[rc(p)] += ftag[p], ftag[rc(p)] += ftag[p];
    ftag[p] = 0;
    return;
}
inline void pushup(int &p){
    ibig[p] = max(ibig[lc(p)],ibig[rc(p)]), ismall[p] = min(ismall[lc(p)],ismall[rc(p)]);
    fbig[p] = max(fbig[lc(p)],fbig[rc(p)]), fsmall[p] = min(fsmall[lc(p)],fsmall[rc(p)]);
    return;
}
void update(int p,int l,int r,int nl,int nr,int bst,char tp){
    if(nl<=l&&r<=nr){
         if(tp=='i') ibig[p] += bst, ismall[p] += bst, itag[p] += bst;
         if(tp=='f') fbig[p] += bst, fsmall[p] += bst, ftag[p] += bst;
         return;
    }
    int mid = (l + r) >> 1;
    pushdown(p);
    if(nl<=mid) update(lc(p),l,mid,nl,nr,bst,tp);
    if(mid+1<=nr) update(rc(p),mid+1,r,nl,nr,bst,tp);
    pushup(p);
    return;
}
const int inf = 0;
node queryans,pos;
void Query(int p,int l,int r){
   // cout << l <<" "<<r << " "<<fbig[p]<<" "<<fsmall[lc(p)]<<" "<<ibig[lc(p)]<<" "<<ismall[p]<<endl;
    int mid = (l + r) >> 1;
    if(l == r){
        queryans = max(queryans,min(ismall[p],fsmall[p]));
        return;
    }
    pushdown(p);
    if(fbig[lc(p)] > ismall[lc(p)] && fsmall[lc(p)] < ibig[lc(p)]){
        Query(lc(p),l,mid);
    }else if(fsmall[lc(p)] >= ibig[lc(p)] ){
        queryans = max(queryans,ibig[lc(p)]);
    }else if(fbig[lc(p)]<=ismall[lc(p)]){
        queryans = max(queryans,fbig[lc(p)]);
    }
    if(fbig[rc(p)] > ismall[rc(p)] && fsmall[rc(p)] < ibig[rc(p)]){
        Query(rc(p),mid+1,r);
    }else if(fsmall[rc(p)] >= ibig[rc(p)] ){
        queryans = max(queryans,ibig[rc(p)]);
    }else if(fbig[rc(p)]<=ismall[rc(p)]){
        queryans = max(queryans,fbig[rc(p)]);
    }
    return;
}
void build(int p,int l,int r){
    if(l==r){
        fbig[p].p=fsmall[p].p=ibig[p].p=ismall[p].p=l;
        return;
    }
    int mid = (l+r) >> 1;
    build(lc(p),l,mid);
    build(rc(p),mid+1,r);
    pushup(p);
    return;
}
inline int r() {
  int c = getchar(), s = 0;
  while (c < 48 || c > 57) c = getchar();
  while (c > 47 && c < 58) s = (s << 3) + (s << 1) + c - 48, c = getchar();
  return s;
}
int main(){
    scanf("%d",&Q);
    for(int i = 1;  i <= Q; i ++ ){
       // scanf("%d%d",&type[i],&t[i]);
       type[i] = r(); t[i] = r();
        if(type[i]==1){
            //scanf("%d%d",&x[i],&y[i]);
            x[i] = r(); y[i] = r();
            s[++tot] = x[i];
        }
    }
    sort(s+1,s+1+tot);
    tot = unique(s+1,s+1+tot) - s - 1;
    build(1,1,tot);
    for(int i = 1 ; i <= Q; i ++ ){
        if(type[i]==1){
            if(t[i]==0){
                I.insert(x[i]);
                update(1,1,tot,POS(x[i]),tot,y[i],'i');
            }else{
                F.insert(x[i]);
                update(1,1,tot,1,POS(x[i]),y[i],'f');
            }
        }
        if(type[i]==2){
            if(t[t[i]]==0){
                I.erase(I.find(x[t[i]]));
                update(1,1,tot,POS(x[t[i]]),tot,-y[t[i]],'i');
            }else{
                F.erase(F.find(x[t[i]]));
                update(1,1,tot,1,POS(x[t[i]]),-y[t[i]],'f');
            }
        }
        if(I.empty()||F.empty()){
            printf("Peace\n");
            continue;
        }else{
            if( (*I.begin()) > (*(prev(F.end()))) ){
                printf("Peace\n");
                continue;
            }else{
                queryans.v = 0;
                Query(1,1,tot);
                printf("%d %lld\n",s[queryans.p],(long long)queryans.v*(long long)2);
            }
        }
    }

    return 0;
}
2023/11/10 22:15
加载中...