2021 CCPC 新疆省赛 补题

给定一个长度为n的数组。定义S[l, r]为[l,r]的区间和，求前w个S[l, r]为多少？

赛时思路。类似于上场的D题，可以直接二分出第w大的值是多少，且所有权值为正值，二分check，对于每个位置i，满足单调性，同样可以使用双指针。得到第w大的值后，再以每一个位置i进行二分 > w的第一个位置，那么答案为此时以当前位置i为左端点，右端点为[l, n]的区间和。

#include
#define ll long long int
using namespace std;
const int N=2e5+10;
ll n,k,a[N];

bool check(ll mid)
{
	int j = 1;
	ll sum = 0;
	ll cnt = 0;
	for(int i = 1 ; i <= n ; i ++)
	{
		while(j <= n && sum + a[j] < mid)
		sum += a[j], j ++;
		if(j <= n && sum + a[j] >= mid)
		cnt += n - j + 1; // i ++
		sum -= a[i];
	}	
	if(cnt >= k)
	return true;
	else return false;
}

ll h[N],valk;
void work1(){
	for(int i=1;i<=n;i++){
		h[i]=h[i-1];
		h[i]+=a[i];
	}
}

vector ve;
void work2(){
	for(int i=1;i<=n;i++){
		if(ve.size()>=k) break;
		int l=i,r=n;
		while(l
			int mid=l+r>>1;
			if(h[mid]-h[i-1]>valk) r=mid;
			else l=mid+1;
		}
		if(h[l]-h[i-1]>valk&&ve.size()
			for(int j=l;j<=n;j++){
				ve.push_back(h[j]-h[i-1]);
				if(ve.size()>=k) break;
			}
		}
	}
}

bool cmp(ll s1,ll s2){
	return s1>s2;
}

int main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	ll l=0,r=1e15;
	while(l
		ll mid=l+r + 1>>1;
		if(check(mid)) l=mid; // 
		else r =mid - 1; 
	}
	valk=l; work1(); work2(); ll si=ve.size(),i;
	sort(ve.begin(),ve.end(),cmp);
	for(i=0;i
		printf("%lld ",ve[i]);
	}
	for(i;i
		printf("%lld ",valk);
	}
	return 0;
} 

题解解法更加巧妙。（关键还简单好写）
首先给定的数组都为非负值，那么第一大的区间和就为[1, n],那么此时第二大的区间和必在[1, n - 1], [2 , n]之间。假设第二大值为[2, n]，那么第三大的备选答案为[2, n - 1]，[3, n], [1, n - 1]。 依次类推，从备选答案中选可利用优先队列，且要注意判重区间。

const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
typedef pair  PII;
ll a[maxn];
struct note{
	int l;
	int r;
	ll sum;
	bool operator < (const note &a) const{
		return sum < a.sum;
	}
};
map  mp;
int main()
{
	int n, w;
	scanf("%d %d", &n, &w);
	ll sum = 0;
	for(int i = 1 ; i <= n ; i ++)
	scanf("%lld", &a[i]), sum += a[i];
	priority_queue  pq;
	pq.push({1, n, sum});
	while(w --)
	{
		note temp = pq.top();
		pq.pop();
		printf("%lld ", temp.sum);
		if(temp.l <= temp.r - 1 && !mp.count({temp.l, temp.r - 1}))
		{
			mp[{temp.l, temp.r - 1}] ++;
			pq.push({temp.l, temp.r - 1,temp.sum - a[temp.r]});
		}
		if(temp.l + 1 <= temp.r && !mp.count({temp.l + 1, temp.r}))
		{
			mp[{temp.l + 1, temp.r}] ++;
			pq.push({temp.l + 1, temp.r, temp.sum - a[temp.l]});
		}
	}
	return 0;
}

给定一棵树，求出以哪个点为根节点，所有点到当前点的贡献最小。
u–>v的贡献为 d i s [ u ] [ v ] 2 ∗ c [ u ] dis[u][v] ^ 2 * c[u] dis[u][v]2∗c[u]

非常明显的换根DP。
赛时因为式子推错了，写的超级复杂。。
树形DP，当前节点i的答案都是由儿子节点推出的。
考虑单点贡献公式是否由规律。（为简便，可直接假定为一条直链）

f[4] = 0
f[3] = c * c * c[4]
f[2] = (b + c) * (b + c) * c[4] + b * b * c[3]
f[1] = (c + b + a) * (c + b + a) * c[4] + (b + a) * (b + a) * c[3] + a * a * c[2]
因为为树形DP，直接考虑和儿子节点关系。
可以发现需要维护sumc[i]:以i点为根的子树中所有点权和（包含i号点）。
sum1[i]:以i号点为根的子树中一次项之和。
f[i]:以i号点为根的子树中的点对i号点的贡献
那么转移方程为:（sta为当前节点）
s u m c [ s t a ] + = s u m c [ s o n ] ; sumc[sta] += sumc[son]; sumc[sta]+=sumc[son];
s u m 1 [ s t a ] + = s u m 1 [ s o n ] + w [ i ] ∗ s u m c [ s o n ] ; sum1[sta] += sum1[son] + w[i] * sumc[son]; sum1[sta]+=sum1[son]+w[i]∗sumc[son];
f [ s t a ] + = f [ s o n ] + s u m c [ s o n ] ∗ w [ i ] ∗ w [ i ] + 2 l l ∗ w [ i ] ∗ s u m 1 [ s o n ] ; f[sta] += f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son]; f[sta]+=f[son]+sumc[son]∗w[i]∗w[i]+2ll∗w[i]∗sum1[son];
之后考虑换根。(换根DP一定要一步一步推！！！）
up[i]:除以i号点为根的子树中点对当前节点i的贡献
S U M C [ s o n ] = S U M C [ s t a ] + s u m c [ s t a ] − s u m c [ s o n ] ; SUMC[son] = SUMC[sta] + sumc[sta] - sumc[son]; SUMC[son]=SUMC[sta]+sumc[sta]−sumc[son];
S U M 1 [ s o n ] = ( S U M 1 [ s t a ] + ( s u m 1 [ s t a ] − s u m 1 [ s o n ] − w [ i ] ∗ s u m c [ s o n ] ) ) + w [ i ] ∗ S U M C [ s o n ] ; SUM1[son] = (SUM1[sta] + (sum1[sta] - sum1[son] - w[i] * sumc[son])) + w[i] * SUMC[son]; SUM1[son]=(SUM1[sta]+(sum1[sta]−sum1[son]−w[i]∗sumc[son]))+w[i]∗SUMC[son];
up[son]由两部分组成。
第一部分为除以sta点为根的子树对当前节点son的贡献
u p [ s o n ] + = u p [ s t a ] + S U M C [ s t a ] ∗ w [ i ] ∗ w [ i ] + 2 l l ∗ w [ i ] ∗ S U M 1 [ s t a ] up[son] += up[sta] + SUMC[sta] * w[i] * w[i] + 2ll * w[i] * SUM1[sta] up[son]+=up[sta]+SUMC[sta]∗w[i]∗w[i]+2ll∗w[i]∗SUM1[sta]
第二部分为以sta点为根的子树且除以son为根的子树对当前节点son的贡献
u p [ s o n ] + = f [ s t a ] − ( f [ s o n ] + s u m c [ s o n ] ∗ w [ i ] ∗ w [ i ] + 2 l l ∗ w [ i ] ∗ s u m 1 [ s o n ] ) + ( s u m c [ s t a ] − s u m c [ s o n ] ) ∗ w [ i ] ∗ w [ i ] + 2 l l ∗ w [ i ] ∗ ( s u m 1 [ s t a ] − s u m 1 [ s o n ] − w [ i ] ∗ s u m c [ s o n ] ) up[son] += f[sta] - (f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son]) + (sumc[sta] - sumc[son]) * w[i] * w[i] + 2ll * w[i] * (sum1[sta] - sum1[son] - w[i] * sumc[son]) up[son]+=f[sta]−(f[son]+sumc[son]∗w[i]∗w[i]+2ll∗w[i]∗sum1[son])+(sumc[sta]−sumc[son])∗w[i]∗w[i]+2ll∗w[i]∗(sum1[sta]−sum1[son]−w[i]∗sumc[son])

const int maxn = 2e5 + 10;
typedef pair  PII;
int h[maxn], ne[maxn * 2], e[maxn * 2], idx;
ll w[maxn * 2], c[maxn], sumc[maxn], sum1[maxn], SUMC[maxn], SUM1[maxn], f[maxn], up[maxn];
void add(int u, int v, ll ww)
{
	w[idx] = ww;
	e[idx] = v;
 	ne[idx] = h[u];
 	h[u] = idx ++;
}
void dfs1(int sta, int fa)
{
	sumc[sta] = c[sta];
	for(int i = h[sta] ; i != -1 ; i = ne[i])
	{
		int son = e[i];
		if(son == fa) continue;
		dfs1(son, sta);
		sumc[sta] += sumc[son];
		sum1[sta] += sum1[son] + w[i] * sumc[son];
		f[sta] += f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son];
	}
}
void dfs2(int sta, int fa)
{
	for(int i = h[sta] ; i != -1; i = ne[i])
	{
		int son = e[i];
		if(son == fa) continue;
		SUMC[son] = SUMC[sta] + sumc[sta] - sumc[son];
		SUM1[son] = (SUM1[sta] + (sum1[sta] - sum1[son] - w[i] * sumc[son])) + w[i] * SUMC[son];
		up[son] = up[sta] + SUMC[sta] * w[i] * w[i] + 2ll * w[i] * SUM1[sta] + f[sta] - (f[son] + sumc[son] * w[i] * w[i] + 2ll * w[i] * sum1[son]) + 
		(sumc[sta] - sumc[son]) * w[i] * w[i] + 2ll * w[i] * (sum1[sta] - sum1[son] - w[i] * sumc[son]);
		dfs2(son, sta);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	memset(h, -1, sizeof(h)), idx = 0;
	for(int i = 1 ; i <= n ; i ++)
	scanf("%lld", &c[i]);
	for(int i = 1 ; i < n ; i ++)
	{
		int u, v;
		ll w;
		scanf("%d %d %lld", &u, &v, &w);
		add(u, v, w), add(v, u, w);		
	}
	dfs1(1, -1), dfs2(1, -1);
	ll res = 2e18;
	for(int i = 1 ; i <= n ; i ++)
	res = min(res, f[i] + up[i]);
	printf("%lldn",res);
	return 0; 
}

∑ i = 1 n ∑ j = 1 n ( a [ i ]    x o r    a [ j ] ) 2 sum_{i = 1} ^ {n}sum_{j = 1}^{n} (a[i] ; xor ;a[j]) ^ 2 ∑i=1n​∑j=1n​(a[i]xora[j])2

考虑xor性质。且经典按位考虑。

先考虑 a [ i ]    x o r    a [ j ] a[i] ; xor ;a[j] a[i]xora[j]

a [ i ]    x o r    a [ j ] = ∑ i = 0 31 2 i    ( a [ i ] > > i & 1 ≠ a [ j ] > > i & 1 ) a[i] ; xor ;a[j] = sum_{i = 0} ^ {31}2^{i};(a[i] >> i & 1 neq a[j] >> i &1) a[i]xora[j]=∑i=031​2i(a[i]>>i&1​=a[j]>>i&1)

那么 ( a [ i ]    x o r    a [ j ] ) ∗ ( a [ i ]    x o r    a [ j ] ) (a[i] ; xor ;a[j]) * (a[i] ; xor ;a[j]) (a[i]xora[j])∗(a[i]xora[j])为

∑ i = 0 31 2 i    ( a [ i ] > > i & 1 ≠ a [ j ] > > i & 1 ) ∗ ∑ j = 0 31 2 j    ( a [ i ] > > j & 1 ≠ a [ j ] > > j & 1 ) sum_{i = 0} ^ {31}2^{i};(a[i] >> i & 1 neq a[j] >> i &1) * sum_{j = 0} ^ {31}2^{j};(a[i] >> j & 1 neq a[j] >> j &1) ∑i=031​2i(a[i]>>i&1​=a[j]>>i&1)∗∑j=031​2j(a[i]>>j&1​=a[j]>>j&1)

∑ i = 0 31 ∑ j = 0 j = 31 2 i + j ( a [ i ] > > i & 1 ≠ a [ j ] > > i & 1 且 a [ i ] > > j & 1 ≠ a [ j ] > > j & 1 ) sum_{i = 0} ^ {31}sum_{j = 0}^{j = 31} 2^{i + j} (a[i] >> i & 1 neq a[j] >> i &1 且 a[i] >> j & 1 neq a[j] >> j &1) ∑i=031​∑j=0j=31​2i+j(a[i]>>i&1​=a[j]>>i&1且a[i]>>j&1​=a[j]>>j&1)

可以发现且题目不考虑顺序。

那么只需要统计出任意两个数字第i位和第j位分别不相同即可。

对 2 i + j 2 ^ {i + j} 2i+j 取模，可以直接预处理。但可能比较懒，且时间复杂度也能过， 在这里直接计算了。

ll a[maxn], f[35][3][35][3];
const ll mod = 1e9 + 7;
ll get_mod1(ll a, ll b)
{
    return (a % mod + b % mod) % mod; 
}
ll get_mod2(ll a, ll b)
{
    return (a % mod * (b % mod)) % mod;
}
ll ksm(ll base, ll power)
{
    ll res = 1;
    while(power)
    {
        if(power & 1)
        res = get_mod2(res, base);
        base = get_mod2(base, base);
        power >>= 1;
    }
    return res;
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 1 ; i <= n ; i ++)
    scanf("%lld", &a[i]);
    for(int i = 1 ; i <= n ; i ++)
    {
        for(int j = 0; j <= 31 ; j ++)
        {
            for(int k = 0; k <= 31 ; k ++)
            {
                f[j][a[i] >> j & 1][k][a[i] >> k & 1] ++;
            }
        }
    }
    ll res = 0;
    for(int i = 0 ; i <= 31 ; i ++)
    {
        for(int j = 0; j <= 31 ; j ++)
        {
            for(int ii = 0; ii <= 1 ; ii ++)
            {
                for(int jj = 0; jj <= 1 ; jj ++)
                {
                    res = get_mod1(res, get_mod2(ksm(2ll, (i + j) * 1ll), get_mod2(f[i][ii][j][jj],f[i][ii ^ 1][j][jj ^ 1])));              
                } 
            }
        }
    }
    printf("%lldn",res % mod);
}