CF EDU ROUND 171

C

贪心

第i个东西只能在i天及以后买，价格i。给一个01串，第i位为1表示第i天可以去买东西，否则表示不能去买。一次买超过一个东西，可以给最贵的哪个免单。问买所有东西的最小花费？

那么可以注意到所有为0的位置对应的东西，肯定不能当天去买，只能在后面某天去买，而后面某天去买的时候，肯定不止买这个东西，肯定还要买更晚发售的才划算，因为这相当于有东西凑单，我们可以让更晚发售的东西免单。但也因此，所有为0的位置的东西，肯定不能免单，我们只能用他们来凑单，让1的的东西免单。

所以我们对于所有1的东西，考虑他们能不能免单。然后又是一个贪心思想：优先用用最难用出去的东西。这里就是说可以用如果用0来个1凑单，我们要用当前可以用的0里面$i$最靠后的，因为一个0只能给他后面的东西凑单，你在这里不用，对于$i$更小的1，这个0更难用出去，如果用不出去，就浪费了一个凑单机会了。

如果没有0了，但是还有1，我们也可以用1凑单，这肯定比不凑单更优，不凑单所有1都不能免单，凑单至少还有一半的1可以免单。然后用哪些1呢？用来凑单的那个1肯定不能免单了，那么这个1的代价越小越好，因此我们要用$i$最小的1。

那我们可以对1的下标分别维护两个队列。每次想用0凑单的时候，就从0队列队尾取，就是$i$最大的0，想用1的时候，就从1队列队首取，就是$i$最小的1。然后从$i$大到小考虑1，也就是从1的队尾开始

void solve(){
	cin>>n;
	string s;
	cin>>s;
	s=' '+s;
	deque<int>q1,q0;
	int ans=0;
	rep(i,1,n){
		ans+=i;
		if(s[i]=='1')q1.push_back(i);
		else q0.push_back(i);
	}
	
	while(q1.size()){
		int x=q1.back();
		q1.pop_back();
		
		while(q0.size()&&q0.back()>x){
			q0.pop_back();
		}
		if(q0.size()){
			ans-=x;
			q0.pop_back();
		}
		else{
			if(q1.size()){
				ans-=x;
				q1.pop_front();
			}
		}
	}
	cout<<ans<<'\n';
}

D

推式子

$sum(l,r)$表示$[l,r]$区间内元素和，现在把所有子区间的$sum$按$(l,r)$的顺序升序排列，得到一个数组，有$q$个查询，每次问这个数组$[l,r]$区间的和。

首先对于$[l,r]$区间查询，我们还是可以先于处理前缀和，然后转化成$cal(r)-cal(l-1)$

然后对于一个$cal(x)$,首先由于子区间很多，$x$可能很大，我们可以二分出来这个x是属于那个块的，并且可以算出来位于所在块的第几个。每个块可以定义为，左端点相同的所有子区间，比如$[1,1],[1,2]...[1,n]$是第一个块。然后显然每个块的和我们是可以快速算出来的，对于左端点为$i$的块，就是$a(i)$出现$n-i+1$次，$a(i-1)$出现$n-i$次……$a(n)$出现$1$次

画个图可能就好理解了，比如有个数组是$1,2,3,4,5$的话，下图就是第一个块的所有元素，其中第$i$行是$s(1,i)$

1
1 2
1 2 3 
1 2 3 4
1 2 3 4 5

然后第2块实际上就是删掉第一列

2
2 3
2 3 4
2 3 4 5

以此类推，我们可以$O(n)$算出来每一块的和

然后对于不满一块的部分的和，还是用这个例子来分析，比如这一部分是$s(2,2),s(2,3),s(2,4)$，那元素实际上就是

2
2 3
2 3 4

记这一段为$f(i,j)$的话，实际上$f(i,j)=sigm{a}_{k=i}^{j}a(k)\ast (j-i+1-(k-i))=sigm{a}_{k=i}^{j}a(k)\ast (j-k+1)=(j+1)\ast sum(a(k))-sum(k\ast a(k))$，可以看到这就分解成了两个东西$a(i),i\ast a(i)$的前缀和，我们维护一下这两个前缀和即可

void solve(){
	cin>>n;
	vi a(n+1),s(n+1),s1(n+1),s2(n+1),s3(n+1);
	rep(i,1,n){
		cin>>a[i];
		s[i]=s[i-1]+a[i];
		s1[i]=s1[i-1]+a[i]*(n-i+1);
		s3[i]=s3[i-1]+a[i]*i;
	}
	rep(i,1,n){
		s2[i]=s2[i-1]+s1[n]-s1[i-1];
	}
	cin>>m;
	auto cal=[&](int x)->int{
		int l=1,r=n;
		auto check=[&](int m)->bool{
			return (2*n-m+1)*m/2<x;
		};
		while(l<=r){
			int m=l+r>>1;
			if(check(m))l=m+1;
			else r=m-1;
		}
		int res=s2[r];//前面所有块的和
		int i=r+1;//在第几块
		int j=x-(2*n-r+1)*r/2+i-1;//块里的位置
		
		res+=(j+1)*(s[j]-s[i-1]);//最后式子里第一项
		res-=s3[j]-s3[i-1];//式子里第二项
		return res;
	};
	rep(i,1,m){
		int l,r;
		cin>>l>>r;
		cout<<cal(r)-cal(l-1)<<'\n';
	}
}