20210809 Merchant,Equation,Rectangle

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

做过，但当时咕了 T3

Merchant

先特判 \(t=0\)，之后斜率一定会起作用。

考虑最终选择的物品集合，它们的斜率和一定大于 \(0\)，因此答案具有单调性，可以二分。

实现的时候注意细节

const int N = 1e6+5;

int n,m;

LL s,k[N],b[N];

LL y[N];

bool check(int x) {

	For(i,1,n) y[i] = k[i] * x + b[i];

	nth_element(y+1,y+m,y+n+1,greater<LL>()); // O(n)找前m大

	LL sum = 0;

	For(i,1,m) {

		if( y[i] >= 0 ) sum += y[i]; // 可能选不满m个

		if( sum >= s ) return 1; // 如果不在这里判会爆LL

	}

	return 0;

}

signed main() {

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

	freopen("merchant.out","w",stdout);

	read(n,m,s);

	For(i,1,n) read(k[i],b[i]);

	if( check(0) ) { puts("0"); return 0; }

	int l = 1, r = 1e9;

	while( l < r ) {

		int mid = l+r>>1;

		if( check(mid) ) r = mid;

		else l = mid+1;

	}

	write(l);

	return iocl();

}

Equation

乍一看不好做，但题目只求 \(x_1\) 的值，可以把每个方程改写成 \(x_i=k_ix_1+b_i\) 的形式，修改时用 BIT 维护 \(b\) 即可。注意分深度的奇偶来判断正负。

const int N = 1e6+5;

int n,q,fa[N],val[N];

int ind,dfn[N],siz[N],k[N];

vector<int> to[N];

struct BIT {

	LL t[N];

	void add(int i,LL x) { for(;i<=n;i+=i&-i)t[i]+=x; }

	void add(int l,int r,LL x) { add(l,x), add(r+1,-x); }

	LL operator [] (int i) { LL res=0; for(;i;i-=i&-i)res+=t[i]; return res; }

} b;

void none() { putchar('n'),putchar('o'),putchar('n'),putchar('e'),putchar(10); }

void inf() { putchar('i'),putchar('n'),putchar('f'),putchar(10); }

void dfs(int u) {

	dfn[u] = ++ind, siz[u] = 1;

	for(int v : to[u]) k[v] = -k[u], dfs(v), siz[u] += siz[v];

	b.add(dfn[u],dfn[u]+siz[u]-1,k[u]*val[u]);

}

signed main() {

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

	freopen("equation.out","w",stdout);

	read(n,q);

	For(i,2,n) {

		read(fa[i]), read(val[i]);

		to[fa[i]].pb(i);

	}

	k[1] = 1, dfs(1);

	while( q-- ) {

		int op; read(op);

		if( op == 1 ) {

			int u,v,s; read(u,v,s);

			int kk = k[u]+k[v]; LL bb = s-k[u]*b[dfn[u]]-k[v]*b[dfn[v]];

			if( !kk ) !bb ? inf() : none();

			else if( bb % kk ) none();

			else !bb ? none() : write(bb/kk);

		} else {

			int u,w; read(u,w);

			b.add(dfn[u],dfn[u]+siz[u]-1,k[u]*(w-val[u])), val[u] = w;

		}

	}

	return iocl();

}

rectangle

发现 \(n\) 很大而值域很小，考虑直接在值域上找矩形。

枚举列来确定矩形左右边界，根据左右边界上的点的纵坐标来确定合法的上下边界。

具体做法

时间复杂度 \(O(2500n\log2500)\)

const int N = 1e4+5, X = 2500, mod = 1e9+7;

int n,cnt[N],mp[X+5][X+5];

bool vis[X+5][X+5];

int ans;

struct BIT {

	int t[X+5];

	void add(int i,int x) { for(;i<=X;i+=i&-i)t[i]+=x; }

	int query(int l,int r) {

		int res=0; for(--l;r>l;r-=r&-r)res+=t[r];

		for(;l>r;l-=l&-l)res-=t[l]; return res; }

} siz[X+5],sum[X+5];

signed main() {

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

	freopen("rectangle.out","w",stdout);

	read(n);

	For(i,1,n) {

		int x; read(x);

		read(mp[x][++cnt[x]]);

	}

	For(i,1,X) {

		sort(mp[i]+1,mp[i]+cnt[i]+1);

		mp[i][cnt[i]+1] = X+1;

	}

	For(r,1,X) if( cnt[r] ) {

		For(i,1,cnt[r]) if( !vis[r][mp[r][i]] ) vis[r][mp[r][i]] = 1,

			siz[r].add(mp[r][i],1), sum[r].add(mp[r][i],mp[r][i]);

		rFor(l,r-1,1) if( cnt[l] ) {

			For(i,1,cnt[l]) if( !vis[r][mp[l][i]] ) vis[r][mp[l][i]] = 1,

				siz[r].add(mp[l][i],1), sum[r].add(mp[l][i],mp[l][i]);

			int i = 1, j = 1, now = max(mp[l][1],mp[r][1]);

			while( mp[l][i+1] <= now ) ++i;

			while( mp[r][j+1] <= now ) ++j;

			while( i <= cnt[l] && j <= cnt[r] ) {

				int up = min(mp[l][i+1],mp[r][j+1]), down = min(mp[l][i],mp[r][j]);

				ans += (r-l) *

					(((LL)sum[r].query(now,up-1) * siz[r].query(1,down) -

					(LL)siz[r].query(now,up-1) * sum[r].query(1,down)) %mod) %mod;

				if( ans >= mod ) ans -= mod;

				now = up;

				if( mp[l][i+1] <= now ) ++i;

				if( mp[r][j+1] <= now ) ++j;

			}

		}

	}

	write(ans);

	return iocl();

}