2018牛客网暑期ACM多校训练营（第六场）I

#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
    #ifdef tokitsukaze
        freopen("TEST.txt","r",stdin);
    #endif
    go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=998244353;
/*********************************  head  *********************************/
struct node
{
    int fi,se;
    node(){}
    node(int l,int r) :fi(l),se(r){}
    friend bool operator<(node a,node b)
    {
        if(a.fi==b.fi) return a.se<b.se;
        return a.fi>b.fi;
    }
    friend bool operator!=(node a,node b)
    {
        return a.fi!=b.fi||a.se!=b.se;
    }
};
set<node> mp[MAX];
PII a[MAX];
int res[MAX],nex[MAX],p[MAX];
void go()
{
    int t,n,m,i,ans,x,tot,time,cas=1;
    node tmp;
    ll pre,now;
    read(t);
    while(t--)
    {
        unordered_map<int,int> id;
        VI xx;
        read(n,m);
        for(i=1;i<=n;i++)
        {
            read(a[i].fi,a[i].se);
            xx.pb(a[i].fi);
            res[i]=0;
            nex[i]=i+1;
            p[i]=i-1;
        }
        sort(all(xx));
        xx.resize(unique(all(xx))-xx.begin());
        for(i=0;i<sz(xx);i++) id[xx[i]]=i+1;
        tot=sz(xx);
        for(i=1;i<=tot;i++) mp[i].clear();
        for(i=1;i<=n;i++) mp[id[a[i].fi]].insert(node(a[i].se,i));
        pre=0;
        printf("Case #%d:\n",cas++);
        for(time=1;time<=m;time++)
        {
            read(x);
            x=(x^pre);
            ans=0;
            now=1;
            for(i=1;i<=tot;i=nex[i])
            {
                if(xx[i-1]>x) break;
                tmp=node(-INF,-INF);
                for(auto &it:mp[i])
                {
                    if(tmp!=node(-INF,-INF)) mp[i].erase(tmp);
                    if(it.fi<x) break;
                    ans++;
                    res[it.se]=time;
                    now=now*it.se%mod;
                    tmp=it;
                }
                if(tmp!=node(-INF,-INF)) mp[i].erase(tmp);
                if(sz(mp[i])==0)
                {
                    nex[p[i]]=nex[i];
                    p[nex[i]]=p[i];
                }
            }
            if(now==1&&res[1]!=time) now=0;
            pre=now;
            printf("%d\n",ans);
        }
        for(i=1;i<=n;i++) printf("%d%c",res[i]," \n"[i==n]);
    }
}