题目分析

如果没有最后的注意事项，此题就是二分裸题。有了注意事项，会有两种思路:

在线：二分天数t，并在主席树上求1~t天中大于d(浪费的时间)的时间之和以及数量，答案即为：sum - d * cnt 无奈写的丑，卡卡只能过6、7个点。

离线：简单考虑，既然要求大于等于d的和以及数量，不妨按照d来排序，再把t也排序。每次将大于等于d的t加入树状数组（记录和以及数量），这样就能直接查出和和数量。 AC。

code

树状数组 AC

#include<bits/stdc++.h>

using namespace std;

const int N = 200005, M = 1000005;

typedef long long ll;

int n, m, anss[N];

int pointer;

typedef pair<int, int> P;

typedef pair<ll, int> ansP;

P t[N];

struct BIT{

	ll sum[N], cnt[N];

	inline void add(int x, ll v, int c){

		for(int i = x; i <= m; i += (i&-i))

			sum[i] += v, cnt[i] += c;

	}

	inline ansP query(int x){

		ansP ret = P(0, 0);

		for(int i = x; i; i -= (i&-i))

			ret.first += sum[i], ret.second += cnt[i];

		return ret;

	}

}bit;

struct node{

	int d, r, id;

	inline bool operator < (const node &b) const{

		return d < b.d;

	}

}s[N];

inline int read(){

    int i = 0, f = 1; char ch = getchar();

    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

    if(ch == '-') f = -1, ch = getchar();

    for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch -'0');

    return i * f;

}

inline void wr(int x){

	if(x < 0) putchar('-'), x = -x;

	if(x > 9) wr(x / 10);

	putchar(x % 10 + '0');

}

inline bool calc(int mid, int d, int r){

    ansP tmp = bit.query(mid);

    ll ret = tmp.first - 1LL * d * tmp.second;

    return ret >= r;

}

int main(){

	n = read(), m = read();

	for(int i = 1; i <= m; i++) t[i].first = read(), t[i].second = i;

	for(int i = 1; i <= n; i++) s[i].d = read(), s[i].r = read(), s[i].id = i;

	sort(t + 1, t + m + 1), sort(s + 1, s + n + 1);

	pointer = m;

	for(int i = n; i >= 1; i--){

		while(t[pointer].first >= s[i].d && pointer >= 1) bit.add(t[pointer].second, t[pointer].first, 1), pointer--;

		int l = 1, r = m, ans = 0;

		while(l <= r){

			int mid = l + r >> 1;

			if(calc(mid, s[i].d, s[i].r)) ans = mid, r = mid - 1;

			else l = mid + 1;

		}

		anss[s[i].id] = ans;

	}

	for(int i = 1; i <= n; i++) wr(anss[i]), putchar(' ');

	return 0;

}

主席树 50 ~ 60

#include<bits/stdc++.h>

using namespace std;

const int N = 200005, M = 1000005;

typedef long long ll;

struct node{

    node *lc, *rc;

    ll sum, cnt;

    inline void upt(){

    	sum = lc->sum + rc->sum;

    	cnt = lc->cnt + rc->cnt;

	}

}pool[N * 20], *tail = pool, *null = pool, *rt[N];

int maxx = -1;

typedef pair<ll, ll> ansP;

int n, m, d[N], rr[N];

int t[N], b[N * 2], len;

ll tsum[N];

inline int read(){

    int i = 0, f = 1; char ch = getchar();

    for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

    if(ch == '-') f = -1, ch = getchar();

    for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch -'0');

    return i * f;

}

inline void wr(int x){

	if(x < 0) putchar('-'), x = -x;

	if(x > 9) wr(x / 10);

	putchar(x % 10 + '0');

}

inline void insert(node *x, node *&y, int l, int r, int v){

    y = ++tail;

    y->lc = x->lc, y->rc = x->rc;

    y->sum = x->sum, y->cnt = x->cnt;

    y->sum += b[v];

    y->cnt++;

    if(l == r) return;

    int mid = l + r >> 1;

    if(v <= mid) insert(x->lc, y->lc, l, mid, v);

    else insert(x->rc, y->rc, mid + 1, r, v);

    y->upt();

}

inline ansP query(node *nl, node *nr, int l, int r, int x, int y){

    if(x <= l && r <= y) return ansP(nr->sum - nl->sum, nr->cnt - nl->cnt);

    int mid = l + r >> 1;

    ansP ret = ansP(0, 0);

    if(x <= mid){

        ansP tmp = query(nl->lc, nr->lc, l, mid, x, y);

        ret.first += tmp.first;

        ret.second += tmp.second;

    }

    if(y > mid){

        ansP tmp = query(nl->rc, nr->rc, mid + 1, r, x, y);

        ret.first += tmp.first;

        ret.second += tmp.second;

    }

    return ret;

}

bool flag;

inline bool calc(int mid, int d, int r){

    ansP tmp = query(rt[0], rt[mid], 1, maxx, d, maxx);

    ll ret = tmp.first - 1LL * b[d] * tmp.second;

    return ret >= r;

}

inline void disc_init(){

    sort(b + 1, b + len + 1);

    len = unique(b + 1, b + len + 1) - (b + 1);

    for(int i = 1; i <= m; i++) t[i] = lower_bound(b + 1, b + len + 1, t[i]) - b;

    for(int i = 1; i <= n; i++) d[i] = lower_bound(b + 1, b + len + 1, d[i]) - b;

}

int main(){

	freopen("h.in", "r", stdin);

	ios::sync_with_stdio(false);

	cin.tie(NULL), cout.tie(NULL);

    n = read(), m = read();

    null->lc = null->rc = null, null->sum = null->cnt = 0;

    for(int i = 1; i <= m; i++) t[i] = b[++len] = read(), maxx = max(maxx, t[i]);

    for(int i = 1; i <= n; i++) d[i] = b[++len] = read(), rr[i] = read();

    disc_init();

    rt[0] = null;

    for(int i = 1; i <= m; i++)

        insert(rt[i - 1], rt[i], 1, maxx, t[i]);

    for(int i = 1; i <= n; i++){

        int l = 1, r = m, ans = 0;

        if(d[i] > maxx){

			putchar('0'),putchar(' ');

			continue;

		}

        while(l <= r){

            int mid = l + r >> 1;

            if(calc(mid, d[i], rr[i])) ans = mid, r = mid - 1;

            else l = mid + 1;

        }

        cout << ans << " ";

    }

}

巴特西

NOIP模拟 Work - 二分 + 树状数组 / ???

题目分析

code

最新文章

热门文章