Codeforces Round #179 (Div. 1)（完全）

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;
}