raiting 又掉了，明天早上爬起来继续搞,hehe
A题：好像用数组打标记的方法更简单，反正我直接套了两个树状数组。。。。
http://codeforces.com/contest/295/submission/3507289
B题：本场比赛的败笔，在更新最短路的时候姿势不够正确，然后交了几遍才过。。
做法就是倒着搞，如果更新了某点对的最短路，就要减去相应的差值。
http://codeforces.com/contest/295/submission/3511531
C题：搜索 + ＤＰ dp[a][b][c]表示这边有a个50公斤的人 b个100公斤的人，c为0表示在这边，为1表示在对岸 的且最快到达这个状态的达到最总方案数，因为要最快，所以是要bfs 过去
http://codeforces.com/contest/295/submission/3514654
D题：题意表述极为恶心，真想拿把刀把出题人砍了.......
所以我还是写的详细点儿吧~
类似于http://codeforces.com/contest/273/problem/D，不过看错题了，开始以为一样的，。。
那个题更难，因为存在以下情况
xx00
0xx0
这样子也是可以的，所以要考虑左右端点的增减性，还要记录左右端点的位置，是三次方的复杂度
而这道题是先是上一行只能是下一行的子集，然后是下一行是上一行的子集。中间有一行或者若干行是最长的（两个黑点的距离最大），然后往上下两边非递增趋势
下面是一种合法的方法
000xxxx0000
00xxxxxx0000
000xxx00000
000xx000000
两个黑点相当于给某一段染色了。。。
n m范围是2000，显然只能O(n^2)。。。
考虑这样的状态f[i][j] 表示前i行第i行长度恰好是j的方案数 g[i][j]表示前i行，第i行的长度小于等于j的方案数
g[i][j] = sigma(f[i][k]*(j-k+1))
这里g[i][j]不能枚举去求，必须O(1)，所以用到了一些小技巧
举个例子
g[i][3] = f[i][1] * 3 + f[i][2] * 2 + f[i][3]
g[i][4] = f[i][1] * 4 + f[i][2] * 3 + f[i][3] * 2 + f[i][4]
g[i][4] = g[i][3] + f[i][1] + f[i][2] + f[i][3] + f[i][4];
然后就应该很好懂了。
注意比如n=2 m=4
f[2][3] = 4;
xx0 0xx xxx 000
xxx xxx xxx xxx
上面可以为空
f[3][2] = 3 ，最后一行一定长度为2
如下
xx
xx xx
xx xx xx
那么求答案的时候 就是枚举最长的那行在哪一行，是多长，然后这一行以下
要么为空（+1）
要么比j短(g[n-i][j]-f[n-i][j])
然后非递增的往下
ans = f[i][j]*(g[n-i][j]-f[n-i][j]+1)*(m-j+1)
#include<cstdio>
#include<cstring>
const int mod = 1000000007;
using namespace std;
int f[2013][2013] , g[2013][2013];
void Add(int &a,int b)
{
a += b;
if(a >= mod) a -= mod;
}
int main()
{
int n , m;
scanf("%d%d",&n,&m);
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
for(int i=1;i<=n;i++)
{
int sum = 0;
for(int j=2;j<=m;j++)
{
Add(f[i][j],g[i-1][j]+1); //上一行可以为空，也就是这一行单独长度为j,所以+1
Add(sum,f[i][j]);
Add(g[i][j],g[i][j-1]+sum);
}
}
// printf("%d\n",f[3][2]);
int ans = 0;
for(int i=1;i<=n;i++)
{
for(int j=2;j<=m;j++)
{
ans += (long long)f[i][j]*(g[n-i][j]-f[n-i][j]+1)%mod*(m-j+1)%mod;
ans%=mod;
}
}
printf("%d\n",ans);
return 0;
}
E题：赤裸裸的数据结构题。。。。。
先给你n个数，x1 x2 x3 x4 x5.....xn
然后有两种操作
1 a b 表示将 xa变成xb
2 l r
也就是所有的大的数减去小的数的和，且这些数都在l r区间里
开始一直在想通过加减操作得出答案，因为以前做过一个题是让你求一段区间内ai * i 的和，但是那个题不需要更新，所以想了一会就被我枪毙掉了。。。。
这道题显然要支持更新操作，那肿么办肿么办，这种线段树题肯定就是想怎么区间合并了。一首先要记录这么几个东西
ans sum cnt
sum是区间和，cnt是区间内有几个数 ans是这段区间的答案
现在考虑合并，其实很简单的，贴一段代码就懂了。。。。。
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
ans[rt] = ans[rt<<1] + ans[rt<<1|1] - sum[rt<<1]*cnt[rt<<1|1] + sum[rt<<1|1]*cnt[rt<<1];
cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];
这道题关键还是要写好查询函数！！注意有些地方超int，我就是这样写傻了，查了半天
然后还有呢？？好像也没了。
速度还是挺快的
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lld;
#define all(v) (v).begin(), (v).end()
#define sqr(x) ((x)*(x))
#define REP(i,n) for(int i = 0; i < n ; i++)
#define REV(s) reverse(s.begin(),s.end())
#define PB push_back
#define MP make_pair
const int maxn = 200010;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
//~segment_tree
vector<int> allx;
struct Seg{
lld sum[maxn<<2];
lld ans[maxn<<2];
int cnt[maxn<<2];
void pushup(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
ans[rt] = ans[rt<<1] + ans[rt<<1|1] - sum[rt<<1]*cnt[rt<<1|1] + sum[rt<<1|1]*cnt[rt<<1];
cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];
}
void build(int l,int r,int rt) {
sum[rt] = 0;
ans[rt] = 0;
cnt[rt] = 0;
if(l==r) return ;
int m = l + r >> 1;
build(lson);
build(rson);
}
void update(int p,int v,int l,int r,int rt) {
if(l==r){
sum[rt] += (lld)allx[p]*v ;
cnt[rt] += v;
ans[rt] = 0;
return ;
}
int m = l + r>>1;
if(p<=m) update(p,v,lson);
else update(p,v,rson);
pushup(rt);
}
pair<pair<lld,lld>,lld> query(int L,int R,int l,int r,int rt){
if(L <= l && r <= R) {
return MP(MP(ans[rt],sum[rt]),cnt[rt]);
}
int m = l + r >>1;
lld ret = 0, lsum = 0 , rsum = 0 , lcnt = 0, rcnt = 0;
if(L <= m) {
pair<pair<lld,lld>,lld> pl = query(L,R,lson);
ret += pl.first.first;
lsum += pl.first.second;
lcnt += pl.second;
}
if(R > m) {
pair<pair<lld,lld>,lld> pr = query(L,R,rson);
ret += pr.first.first;
rsum += pr.first.second;
rcnt += pr.second;
}
return MP(MP(ret - lsum*rcnt + rsum*lcnt,lsum+rsum),lcnt+rcnt);
}
}seg;
struct query {
int t,l,r;
}q[maxn];
int n , m , tot;
int num[maxn];
int getid(int num) {
return lower_bound(all(allx),num) - allx.begin();
}
int p[maxn] , d[maxn];
int main()
{
int t , l ,r , a;
scanf("%d",&n);
vector<int> tx,cx;
REP(i,n){
scanf("%d",&num[i]);
allx.PB(num[i]);
tx.PB(num[i]);
}
cx = tx;
scanf("%d",&m);
REP(i,m){
scanf("%d%d%d",&q[i].t,&q[i].l,&q[i].r);
if(q[i].t==1){
int p = q[i].l , d = q[i].r;
p--;
tx[p] += d;
allx.PB(tx[p]);
}
}
tx=cx;
sort(all(allx));
allx.erase(unique(all(allx)),allx.end());
tot = allx.size();
seg.build(0,tot,1);
REP(i,n){
int id = getid(num[i]);
seg.update(id,1,0,tot,1);
}
REP(i,m){
if(q[i].t == 1){
int p = q[i].l , d = q[i].r;
p --;
int val = tx[p];
tx[p] += d;
int id1 = getid(val);
int id2 = getid(tx[p]);
seg.update(id1,-1,0,tot,1);
seg.update(id2,1,0,tot,1);
}
else {
int l = q[i].l , r = q[i].r;
l = lower_bound(allx.begin(),allx.end(),q[i].l) - allx.begin();
r = upper_bound(allx.begin(),allx.end(),q[i].r) - allx.begin();
r--;if(l>r) {puts("0");continue;}
pair<pair<lld,lld>,lld> ans = seg.query(l,r,0,tot,1);
printf("%I64d\n",ans.first.first);
}
}
return 0;
}
![Codeforces Round #633 (Div. 2) B. Sorted Adjacent Differences（排序，思维）[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)