寒假第一场

新年礼物

int n,p[(int)1e5+9],w[(int)1e5+9]; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    f(i,1,n)cin>>p[i];
    f(i,1,n)cin>>w[i];
    int lst=0,ans=0;
    f(i,1,n){
    	if(p[lst]<p[i]){
    		ans+=w[lst]>w[i];
    		lst=i;
    	}
    }
    cout<<ans;
    return 0;
}

灯笼展

const int maxn=2e5+9;
int n,m,rt[maxn],cnt,b[maxn],a[maxn],tot;
struct Node{
	int l,r,val;
}tr[maxn*20];

inline void build(int &k,int l,int r){
	k=++cnt;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(tr[k].l,l,mid),build(tr[k].r,mid+1,r);
}


inline void change(int &k,int kk,int l,int r,int val){
	k=++cnt,tr[k]=tr[kk],tr[k].val+=1;
	if(l==r)return ;
	int mid=(l+r)>>1;
	if(val<=mid)change(tr[k].l,tr[kk].l,l,mid,val);
	else change(tr[k].r,tr[kk].r,mid+1,r,val);
}

inline int query(int nl,int nr,int l,int r,int k){
	int x=tr[tr[nr].l].val-tr[tr[nl].l].val;
	if(l==r)return b[l];
	int mid=(l+r)>>1;
	if(x>=k)return query(tr[nl].l,tr[nr].l,l,mid,k);
	return query(tr[nl].r,tr[nr].r,mid+1,r,k-x);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f(i,1,n)cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    tot=unique(b+1,b+n+1)-(b+1);
    build(rt[0],1,tot);
    f(i,1,n){
    	int now=lower_bound(b+1,b+1+tot,a[i])-b;
    	change(rt[i],rt[i-1],1,tot,now);
    }
    /*f(i,1,n){
    	int now=lower_bound(b+1,b+1+tot,a[i])-b;
    	change(rt[i],rt[i-1],1,tot,now);
    }
    for(int i=1,l,r,k;i<=m;++i){
    	cin>>l>>r>>k;
    	cout<<query(rt[l-1],rt[r],1,tot,k)<<"\n";
    }*/
    for(int i=1;i<=m;++i)cout<<"-1\n";
    for(int i=m+1;i<=n;++i){
    	int qq=query(rt[0],rt[i-1],1,tot,m);
    	cout<<(qq<=a[i]?qq:-1)<<"\n";
    }
    return 0;
}

新年大礼

ll n,m,a[(int)1e5+9]; 

ll check(ll x){
	ll cz=lower_bound(a+1,a+1+n,x)-(a+1);
	return x-cz;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    f(i,1,n)cin>>a[i];
    sort(a+1,a+1+n);
    for(ll i=1,x;i<=m;++i){
    	cin>>x;
    	ll tmp=0;
    	ll l=1,r=1e18;
    	while(l<r){
    		ll mid=(l+r+1)>>1;
    		if(check(mid)<=x)l=mid;
    		else r=mid-1;
    	}
    	cout<<l<<"\n";
    }
    return 0;
}

摩天楼

ll n,ans[(int)1e6+9];
string s;
ll x;
struct opt{
	int sta;//0 1 2
	ll val;
	vector<int> tim;
}op[(int)1e6+9];

void dfs(int u,vector<int> v){
	//cerr<<u<<"::\n";
	//cerr<<u<<"::"<<v.size()<<"\n";
	if(op[u].sta==0){
		v.push_back(op[u].val);
		ans[u]=op[u].val;
		//cerr<<"\n"<<u<<"::"<<op[u].val<<"??\n";
	}else if(op[u].sta==1){
		if(!v.empty())v.erase(v.end()-1);
		if(v.empty())ans[u]=-1;
		else ans[u]=v.back();
	}else{
		if(v.empty())ans[u]=-1;
		else ans[u]=v.back();
	}
	for(auto it:op[u].tim){
		dfs(it,v);
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i){
    	cin>>s;
    	//cerr<<s<<"???";
    	if(s=="ADD"){
    		cin>>x;
    		op[i].sta=0,op[i].val=x;
    		op[i-1].tim.push_back(i);
    		//cerr<<(i-1)<<"??";
    	}else if(s=="REMOVE"){
    		op[i].sta=1;
    		op[i-1].tim.push_back(i);
    	}else{
    		cin>>x;
    		op[i].sta=2;
    		op[x].tim.push_back(i);
    	}
    }
    vector<int> v;
    dfs(1,v);
    f(i,1,n)cout<<ans[i]<<"\n";
    return 0;
}

神抽

template <int MOD, int RT>
struct mint
{
    static const int mod = MOD;
    static constexpr mint rt() { return RT; } // primitive root for FFT
    int v;
    explicit operator int() const { return v; } // explicit -> don't silently convert to int
    mint() : v(0) {}
    mint(ll _v)
    {
        v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD);
        if (v < 0)
            v += MOD;
    }
    bool operator==(const mint &o) const
    {
        return v == o.v;
    }
    friend bool operator!=(const mint &a, const mint &b)
    {
        return !(a == b);
    }
    friend bool operator<(const mint &a, const mint &b)
    {
        return a.v < b.v;
    }

    mint &operator+=(const mint &o)
    {
        if ((v += o.v) >= MOD)
            v -= MOD;
        return *this;
    }
    mint &operator-=(const mint &o)
    {
        if ((v -= o.v) < 0)
            v += MOD;
        return *this;
    }
    mint &operator*=(const mint &o)
    {
        v = int((ll)v * o.v % MOD);
        return *this;
    }
    mint &operator/=(const mint &o) { return (*this) *= inv(o); }
    friend mint pow(mint a, ll p)
    {
        mint ans = 1;
        assert(p >= 0);
        for (; p; p /= 2, a *= a)
            if (p & 1)
                ans *= a;
        return ans;
    }
    friend mint inv(const mint &a)
    {
        assert(a.v != 0);
        return pow(a, MOD - 2);
    }

    mint operator-() const { return mint(-v); }
    mint &operator++() { return *this += 1; }
    mint &operator--() { return *this -= 1; }
    friend mint operator+(mint a, const mint &b) { return a += b; }
    friend mint operator-(mint a, const mint &b) { return a -= b; }
    friend mint operator*(mint a, const mint &b) { return a *= b; }
    friend mint operator/(mint a, const mint &b) { return a /= b; }
};

using mi = mint<mod, 3>;



ll n;
mi ans,cnt[(int)1e6+9];
vector<mi> v[(int)1e6+9];


mi solve(int x){
    mi res=0;
    for(auto it:v[x]){
        res+=it*cnt[x];
    }
    return res;
}


int main()
{

    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cnt[i]=0;
    for(int i=1,x;i<=n;++i){
        cin>>x;
        map<ll,ll> cn;
        for(ll j=1,y;j<=x;++j){
            cin>>y;
            cn[y]+=1;
        }
        for(auto [aa,bb]:cn){
            v[aa].push_back(mi(1)*mi(bb)*inv(mi(x)));
            cnt[aa]+=1;
        }
    }
    mi cs=inv(mi(n))*inv(mi(n));
    for(int i=1;i<=1e6;++i){
        ans=(ans+solve(i));
    }
    ans=ans*cs;
    cout<<ans.v;
}