Codeforces Round #163 (Div. 二)（完全）
这场比赛大概是我做CF以来最难的一场div2了
D题搞了很久，还是没搞出来，C题题目没看仔细，E题做过类似的，但显然我这种div2选手很少在比赛搞E题，不过现在已经渐渐消除了对后面两题的恐惧、
C.Below the Diagonal
给你一个0 1 方阵，题目说有n-1个1，然后一次操作可以交换两行或者两列，然后要求输出一种交换的方案使得所有的1都在主对角线以下。
可以暴力两个循环先将矩阵调节为从左往右每一列的1的数量非递增，然后接下来从最后一列开始往前处理，枚举这一列主对角线以上（包括对角线）的每一个1，将它们依次填入主对角线下面的每一个空位上（交换两行），第i列的1的数量保证不会超过n-i ， 总数就是n-1，而且从左往右递减，然后想想就知道了。这样子继续交换下去，知道第一列，注意，已经交换过的行不能再换了，因为有可能将已经换到对角线下面的1换回到对角线上面，最坏情况有n-1列被标记掉，所以不用担心交换不下来。
code
D. BerDonalds
一幅图，200个点，n^2条边，现在要找一个点，这个点可以存在于边上，并不局限于给你的那些点，这个点到每个点的最短路的最大值记为M,现在要你输出最小的M。
这里有一个单调性，当ans越大时，满足条件的点就越多（即这个点的M值<=ans），所以可以二分答案+判定，判定时可以枚举每一条边，再枚举所有的点，对于每一个点判断是否有点可以存在于这条边上，且到达这个点的最短距离 <= ans ,ans为二分枚举的答案。具体判断的时候可以记录一下对于当前点，枚举的那条边上会有一个区间是无法在ans的距离内到达当前点的，记录下所有这样的非法区间，如果最后没有完全覆盖枚举的那条边，就证明当前枚举的答案是可行的，因为在某一条边上存在某个点到每个点的最短路径的距离都小于等于ans。
code
E. More Queries to Array...
题意很简单，也很裸，就是区间更新，区间查询
其实只要将题目要求的那个和拆开就知道了
ai * (i-L+1)^k = [ i+(1-L) ] ^ k = C(k,0) * i^k + C(k,1) * i ^ (k-1) * (1-L)......
对于这个式子的每一项只需要区间求和就好了，所以线段树需要维护区间内 ai * （i ^ j）的和(0<=j<=5)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long lld;
const int maxn = 100010;
const int mod = 1000000007;
lld p[6][maxn] , s[6][maxn];
int c[10][10];
int n , m;
int a[maxn];
struct segtree{
int sum[6][maxn<<2];
lld flag[maxn<<2];
lld Pow(int a,int b)
{
lld ans = 1;
for(int i = 1; i <= b; i++) ans = ans * a % mod;
return ans ;
}
void init()
{
c[0][0] = 1;
for(int i = 1; i < 6; i++){
c[i][i] = 1;
for(int j = 0; j < i; j++) c[i][j] = c[i-1][j] + c[i-1][j-1] ;
}
for(int i = 1; i < maxn; i++) for(int j = 0; j < 6; j++) p[j][i] = Pow(i,j);
for(int i = 1; i < maxn; i++)
for(int j = 0; j < 6; j++)
s[j][i] = (s[j][i-1] + p[j][i] ) % mod ;
}
void build(int l,int r,int rt)
{
flag[rt] = -1;
if(l == r) {
for(int i = 0; i < 6; i++)
sum[i][rt] = p[i][l] * a[l] % mod;
} else {
int m = l + r>>1;
build(lson);
build(rson);
pushup(rt);
}
}
void pushdown(int rt,int l,int r)
{
int m = l + r >> 1 , ls = rt<<1 , rs = ls|1;
if(~flag[rt]) {
for(int i = 0; i < 6; i++) {
sum[i][ls] = ( flag[rt] * (s[i][m] - s[i][l-1]) % mod + mod ) % mod;
sum[i][rs] = ( flag[rt] * (s[i][r] - s[i][m] ) % mod + mod ) % mod;
}
flag[ls] = flag[rs] = flag[rt];
flag[rt] = -1;
}
}
void pushup(int rt)
{
int ls = rt<<1 , rs = rt<<1|1;
for(int i = 0; i < 6; i++)
sum[i][rt] = (sum[i][ls] + sum[i][rs])%mod ;
}
void update(int L,int R,int val,int l,int r,int rt)
{
if(L <= l && r <= R){
flag[rt] = val;
for(int i = 0; i < 6; i++)
sum[i][rt] = (flag[rt] * (s[i][r] - s[i][l-1]) % mod + mod ) % mod;
return ;
}
pushdown(rt,l,r);
int m = l + r>>1;
if(L <= m) update(L,R,val,lson);
if(R > m) update(L,R,val,rson);
pushup(rt);
}
int query(int L,int R,int dem,int l,int r,int rt)
{
if(L <= l && r <= R) {
return sum[dem][rt];
}
pushdown(rt,l,r);
int m = l + r >> 1;
int ans = 0;
if(L <= m) ans = (ans + query(L,R,dem,lson))%mod;
if(R > m) ans = (ans + query(L,R,dem,rson))%mod;
return ans ;
}
}st;
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
st.init(); st.build(1,n,1);
char op[5];
int l ,r ,x , k;
while(m--)
{
scanf("%s",op);
scanf("%d%d%d",&l,&r,&k);
if(op[0] == '?')
{
long long ans = 0;
long long tmp = 1;
for(int i = 0; i <= k; i++)
{
ans += (lld)st.query(l,r,k-i,1,n,1) * c[k][i] % mod * tmp % mod;
ans %= mod;
tmp = tmp * (1-l) % mod;
}
printf("%I64d\n",(ans+mod)%mod);
}
else
{
st.update(l,r,k,1,n,1);
}
}
return 0;
}