C++14(g++5.4) 解法, 执行用时: 793ms, 内存消耗: 15968K, 提交时间: 2018-08-12 15:24:16

#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 200002
#define P 998244353
#define INF 1000000007
using namespace std;
int T,Case,n,m,t,a[N],b[N],p[N],ans[N],A[N*4],B[N*4];
long long lst;
bool cmp(int x,int y){return a[x]+b[x]<a[y]+b[y];}
void build(int k,int l,int r){
    if(l==r){
        A[k]=a[p[l]],B[k]=b[p[l]];
        return;
    }
    int mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    A[k]=min(A[k*2],A[k*2+1]);
    B[k]=max(B[k*2],B[k*2+1]);
}
int count(int k,int l,int r,int x){
    if(x<A[k] || x>B[k])return 0;
    if(l==r){
        lst=lst*p[l]%P,ans[p[l]]=t;
        A[k]=INF,B[k]=-INF;
        return 1;
    }
    int res=0,mid=(l+r)>>1;
    if(x>=A[k*2] && x<=B[k*2])res+=count(k*2,l,mid,x);
    if(x>=A[k*2+1] && x<=B[k*2+1])res+=count(k*2+1,mid+1,r,x);
    A[k]=min(A[k*2],A[k*2+1]);
    B[k]=max(B[k*2],B[k*2+1]);
    return res;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%d%d",&a[i],&b[i]);
        printf("Case #%d:\n",++Case);
        for(int i=1;i<=n;++i)ans[p[i]=i]=0;
        sort(p+1,p+n+1,cmp);
        build(1,1,n);
        lst=0;
        for(t=1;t<=m;++t){
            int x;
            scanf("%d",&x),x^=lst,lst=1;
            int res=count(1,1,n,x);
            if(!res)lst=0;
            printf("%d\n",res);
        }
        for(int i=1;i<=n;++i)printf("%d ",ans[i]);
        printf("\n");
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 1451ms, 内存消耗: 43968K, 提交时间: 2018-08-05 18:53:45

#include<bits/stdc++.h>

const int N = 200010;
using namespace std;

int n, m, x[N], y[N];
int t[N], tot, o[N], v[N];
vector<int> c[N];

int main() {
	int Tc;
	scanf("%d", &Tc);
	for(int tc = 1; tc <= Tc; ++tc) {
		printf("Case #%d:\n", tc);
		scanf("%d%d", &n, &m);
		tot = 0;
		for(int i = 1; i <= n; ++i) {
			scanf("%d%d", x + i, y + i);
			t[tot++] = x[i];
		}
		sort(t, t + tot);
		tot = unique(t, t + tot) - t;
		for(int i = 1; i <= n; ++i) {
			o[i] = i;
			x[i] = lower_bound(t, t + tot, x[i]) - t + 1;
			c[i].clear();
			v[i] = 0;
		}
		sort(o + 1, o + 1 + n, [&](int i, int j) {
			return y[i] < y[j];
		}); // y[i] -> o[i]-th
		for(int i = 1; i <= n; ++i) {
			int j = o[i];
			for(int k = x[j]; k <= n; k += k & -k) {
				c[k].emplace_back(j);
			}
		}
		int res = 0;
		for(int i = 1, x; i <= m; ++i) {
			scanf("%d", &x);
			x ^= res;
			int j = upper_bound(t, t + tot, x) - t; // + 1 - 1
			int cnt = 0;
			res = 1;
			for(int k = j; k > 0; k -= k & -k) {
				while(!c[k].empty() && y[c[k].back()] >= x) {
					int u = c[k].back();
					if(!v[u]) {
						v[u] = i;
						++cnt;
						res = 1LL * u * res % 998244353;
					}
					c[k].pop_back();
				}
			}
			printf("%d\n", cnt);
			if(cnt == 0) res = 0;
		}
		for(int i = 1; i <= n; ++i) {
			printf("%d%c", v[i], " \n"[i == n]);
		}
	}
	return 0;
}