2 solutions

  • 0
    @ 2023-11-19 21:39:56
    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    
    typedef struct Function_tag {
    	ll k;
    	ll b;
    	
    	Function_tag(){}
    	
    	Function_tag(ll k_, ll b_){
    		k = k_;
    		b = b_;
    	}
    	
    	inline ull calc(int x){
    		return (ull)k * x + b;
    	}
    } Function;
    
    int cnt[300007], a[300007], b[300007], c[300007], d[300007], e[300007];
    ll l[300007];
    Function f[300007], g[300007], h[300007];
    
    Function operator +(const Function a, const Function b){
    	return Function(a.k + b.k, a.b + b.b);
    }
    
    Function operator +=(Function &a, const Function b){
    	return a = a + b;
    }
    
    Function operator -(const Function a, const Function b){
    	return Function(a.k - b.k, a.b - b.b);
    }
    
    Function operator -=(Function &a, const Function b){
    	return a = a - b;
    }
    
    inline int read(){
    	int ans = 0;
    	char ch = getchar();
    	while (ch < '0' || ch > '9'){
    		ch = getchar();
    	}
    	while (ch >= '0' && ch <= '9'){
    		ans = ans * 10 + (ch ^ 48);
    		ch = getchar();
    	}
    	return ans;
    }
    
    int main(){
    	int n = read(), m = read(), q = read(), x = 0;
    	l[++x] = 1;
    	for (register int i = 1; i <= n; i++){
    		int p = read();
    		cnt[p]++;
    	}
    	for (register int i = 1; i <= m; i++){
    		a[i] = read();
    	}
    	for (register int i = 1; i <= m; i++){
    		b[i] = read();
    	}
    	for (register int i = 1; i <= m; i++){
    		c[i] = read();
    	}
    	for (register int i = 1; i <= m; i++){
    		d[i] = read();
    	}
    	for (register int i = 1; i <= m; i++){
    		e[i] = read();
    	}
    	for (register int i = 1; i <= m; i++){
    		if (cnt[i] > 0){
    			ll pos;
    			f[i].k = d[i];
    			f[i].b = (ll)a[i] * cnt[i];
    			g[i].k = e[i];
    			g[i].b = b[i] + (ll)c[i] * cnt[i];
    			pos = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
    			if (pos >= 1) l[++x] = pos;
    		}
    	}
    	sort(l + 1, l + x + 1);
    	x = unique(l + 1, l + x + 1) - l - 1;
    	for (register int i = 1; i <= m; i++){
    		if (cnt[i] > 0){
    			ll pos1 = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
    			if (pos1 <= 0){
    				h[1] += f[i];
    			} else {
    				int pos2 = lower_bound(l + 1, l + x + 1, pos1) - l;
    				h[1] += g[i];
    				h[pos2] -= g[i];
    				h[pos2] += f[i];
    			}
    		}
    	}
    	for (register int i = 1; i <= x; i++){
    		h[i] += h[i - 1];
    	}
    	for (register int i = 1; i <= q; i++){
    		int k = read();
    		cout << h[upper_bound(l + 1, l + x + 1, k) - l - 1].calc(k) << endl;
    	}
    	return 0;
    }
    
    
    • -1
      @ 2023-6-10 22:51:24

      说句闲话,这个 idea 是我在中考前背政治时想到的。

      首先注意到每个知识点独立,则我们分别算出每个知识点对应的答案后加起来即可。下面我们考虑某个知识点 ii 的情况。

      cnticnt_i 表示 aj=ia_j = ijj 数量,则有:

      • 不标注:aicnti+kdia_i cnt_i + k d_i
      • 标注:bi+cicnti+keib_i + c_i cnt_i + k e_i

      注意 cnti=0cnt_i = 0 者的贡献不会计入答案。

      于是答案为 $\displaystyle\sum_{i = 1}^m [cnt_i > 0] \min(a_i cnt_i + k d_i, b_i + c_i cnt_i + k e_i)$。但直接计算是 O(nq)O(nq) 的,显然不能通过。

      注意到每个 ii 对应的贡献为两个关于 kk 的一次函数,考虑找出一个分界点 x0x_0 使得 kx0\forall k \leq x_0min\min 会取到标注的情况且 k>x0\forall k > x_0min\min 会取到不标注的情况。

      对所有分界点离散化后差分求出每个离散化区间内的答案的一次项和常数项,每次询问时代入回答即可。时间复杂度为 O(n+(m+q)logm)O(n + (m + q) \log m)

      记得开 unsigned long long,不然会 WA on #10。

      代码:

      #include <iostream>
      #include <algorithm>
      #include <cstdio>
      
      using namespace std;
      
      typedef long long ll;
      typedef unsigned long long ull;
      
      typedef struct Function_tag {
      	ll k;
      	ll b;
      	
      	Function_tag(){}
      	
      	Function_tag(ll k_, ll b_){
      		k = k_;
      		b = b_;
      	}
      	
      	inline ull calc(int x){
      		return (ull)k * x + b;
      	}
      } Function;
      
      int cnt[300007], a[300007], b[300007], c[300007], d[300007], e[300007];
      ll l[300007];
      Function f[300007], g[300007], h[300007];
      
      Function operator +(const Function a, const Function b){
      	return Function(a.k + b.k, a.b + b.b);
      }
      
      Function operator +=(Function &a, const Function b){
      	return a = a + b;
      }
      
      Function operator -(const Function a, const Function b){
      	return Function(a.k - b.k, a.b - b.b);
      }
      
      Function operator -=(Function &a, const Function b){
      	return a = a - b;
      }
      
      inline int read(){
      	int ans = 0;
      	char ch = getchar();
      	while (ch < '0' || ch > '9'){
      		ch = getchar();
      	}
      	while (ch >= '0' && ch <= '9'){
      		ans = ans * 10 + (ch ^ 48);
      		ch = getchar();
      	}
      	return ans;
      }
      
      int main(){
      	int n = read(), m = read(), q = read(), x = 0;
      	l[++x] = 1;
      	for (register int i = 1; i <= n; i++){
      		int p = read();
      		cnt[p]++;
      	}
      	for (register int i = 1; i <= m; i++){
      		a[i] = read();
      	}
      	for (register int i = 1; i <= m; i++){
      		b[i] = read();
      	}
      	for (register int i = 1; i <= m; i++){
      		c[i] = read();
      	}
      	for (register int i = 1; i <= m; i++){
      		d[i] = read();
      	}
      	for (register int i = 1; i <= m; i++){
      		e[i] = read();
      	}
      	for (register int i = 1; i <= m; i++){
      		if (cnt[i] > 0){
      			ll pos;
      			f[i].k = d[i];
      			f[i].b = (ll)a[i] * cnt[i];
      			g[i].k = e[i];
      			g[i].b = b[i] + (ll)c[i] * cnt[i];
      			pos = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
      			if (pos >= 1) l[++x] = pos;
      		}
      	}
      	sort(l + 1, l + x + 1);
      	x = unique(l + 1, l + x + 1) - l - 1;
      	for (register int i = 1; i <= m; i++){
      		if (cnt[i] > 0){
      			ll pos1 = (f[i].b - g[i].b) / (g[i].k - f[i].k) + 1;
      			if (pos1 <= 0){
      				h[1] += f[i];
      			} else {
      				int pos2 = lower_bound(l + 1, l + x + 1, pos1) - l;
      				h[1] += g[i];
      				h[pos2] -= g[i];
      				h[pos2] += f[i];
      			}
      		}
      	}
      	for (register int i = 1; i <= x; i++){
      		h[i] += h[i - 1];
      	}
      	for (register int i = 1; i <= q; i++){
      		int k = read();
      		cout << h[upper_bound(l + 1, l + x + 1, k) - l - 1].calc(k) << endl;
      	}
      	return 0;
      }
      
      • 1

      Information

      ID
      279
      Time
      1000ms
      Memory
      512MiB
      Difficulty
      6
      Tags
      (None)
      # Submissions
      50
      Accepted
      17
      Uploaded By