### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

public:
long long solve(long long L, long long R, int K) {
return Cal(R - K, K) - Cal(L - 1 - K, K);
}
private:
inline LL Cal(LL n, int k) {
if (n <= 0) {
return 0;
} else {
LL ret = Cal((n - k) >> 1, k) << 1;
ret += n + (n >> 1);
for (LL i=((n-k)>>1)+1;i*2<=n;i++) {
ret += g(i + k, k);
}
return ret;
}
}
inline int g(LL x, int k) {
LL ret = 0, w = x;
while (w > k) {
++ret;
w = (((w&1)? (w+k): (w>>1)));
}
return ret;
}
};

## 【BZOJ 4826】[HNOI2017] 影魔

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int NN = N << 1;
const int M = 18;

int n,m,p1,p2,val[N];
LL ans[N];
vector<int> q1[N];
vector<pair<int,int> > q2[N],q3[N];
struct Query{int l,r,id;}q[N];

inline bool cmp1(const Query &A, const Query &B) {return A.r < B.r;}
inline bool cmp2(const Query &A, const Query &B) {return A.l > B.l;}

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

class Sparse_Table{
int mx[M][N],pos[M][N],lg[N];
public:
inline void init(int *arr) {
for (int i=1;i<=n;i++) {
mx[0][i] = arr[i];
pos[0][i] = i;
}
for (int l=1,j=1;l*2<=n;j++,l<<=1) {
for (int i=1;i<=n-l;i++) {
if (mx[j-1][i] >= mx[j-1][i+l]) {
pos[j][i] = pos[j-1][i];
mx[j][i] = mx[j-1][i];
} else {
pos[j][i] = pos[j-1][i+l];
mx[j][i] = mx[j-1][i+l];
}
}
}
for (int i=2;i<=n;i++) {
lg[i] = lg[i>>1] + 1;
}
}
inline int query(int l, int r) {
int t = lg[r-l+1], j = 1 << t;
if (mx[t][l] >= mx[t][r-j+1]) return pos[t][l];
else return pos[t][r-j+1];
}
}ST;

void solve(int l, int r) {
if (l == r - 1) {
return;
} else {
int pos = ST.query(l+1, r-1);
if (l) q1[pos].push_back(l);
if (r <= n) q1[r].push_back(pos);

if (r <= n && pos - l > 1) q2[r].push_back(make_pair(l + 1, pos - 1));
if (l && r - pos > 1) q3[l].push_back(make_pair(pos + 1, r - 1));

solve(l, pos);
solve(pos, r);
}
}

class Segment_Tree{
int cnt; LL AnsTmp;
struct Node{
Node *ch[2];
int len;
LL sum,tag;
}p[NN],*root;
public:
inline void init() {
cnt = 0;
build(root, 1, n);
}
inline void modify(int pos, int delta) {
Node *w = root;
int  l = 1, r = n, mid;
while (l <= r) {
w->sum += delta;
if (l == r) break;
mid = l + r + 1 >> 1;
if (pos < mid) w = w->ch[0], r = mid - 1;
else w = w->ch[1], l = mid;
}
}
inline void modify(int l, int r, int delta) {
modify(root, 1, n, l, r, delta);
}
inline LL query(int l, int r) {
AnsTmp = 0;
query(root, 1, n, l, r);
return AnsTmp;
}
private:
inline void pushdown(Node *w) {
w->ch[0]->sum += w->ch[0]->len * w->tag;
w->ch[1]->sum += w->ch[1]->len * w->tag;
w->ch[0]->tag += w->tag; w->ch[1]->tag += w->tag;
w->tag = 0;
}
void query(Node *w, int l, int r, int L, int R) {
if (L <= l && r <= R) {
AnsTmp += w->sum;
} else {
if (w->tag) pushdown(w);
int mid = l + r + 1 >> 1;
if (L < mid) query(w->ch[0], l, mid-1, L, R);
if (mid <= R) query(w->ch[1], mid, r, L, R);
}
}
void modify(Node *w, int l, int r, int L, int R, int delta) {
if (L <= l && r <= R) {
w->sum += (LL)delta * w->len;
w->tag += delta;
} else {
if (w->tag) pushdown(w);
int mid = r + l + 1 >> 1;
if (L < mid) modify(w->ch[0], l, mid-1, L, R, delta);
if (mid <= R) modify(w->ch[1], mid, r, L, R, delta);
w->sum = w->ch[0]->sum + w->ch[1]->sum;
}
}
void build(Node *&w, int l, int r) {
w = &p[++cnt];
w->len = r - l + 1;
w->sum = w->tag = 0;
w->ch[0] = w->ch[1] = 0;
if (l < r) {
int mid = l + r + 1 >> 1;
build(w->ch[0], l, mid-1);
build(w->ch[1], mid, r);
}
}
}SEG;

int main() {
for (int i=1;i<=n;i++) {
}
ST.init(val);
solve(0, n+1);
for (int i=1;i<=m;i++) {
q[i].id = i;
}
sort(q+1, q+1+m, cmp1);
SEG.init();
for (int i=1,pos=0;i<=m;i++) {
while (pos < q[i].r) {
pos++;
for (int j=0;j<q1[pos].size();j++) {
SEG.modify(q1[pos][j], p1);
}
for (int j=0;j<q2[pos].size();j++) {
SEG.modify(q2[pos][j].first, q2[pos][j].second, p2);
}
}
ans[q[i].id] += SEG.query(q[i].l, q[i].r);
}
sort(q+1, q+1+m, cmp2);
SEG.init();
for (int i=1,pos=n+1;i<=m;i++) {
while (pos > q[i].l) {
pos--;
for (int j=0;j<q3[pos].size();j++) {
SEG.modify(q3[pos][j].first, q3[pos][j].second, p2);
}
}
ans[q[i].id] += SEG.query(q[i].l, q[i].r);
}
for (int i=1;i<=m;i++) {
printf("%lld\n",ans[i]);
}
return 0;
}

## 【BZOJ 3711】[PA2014] Druzyny

### 解题报告

1. $g_i \le l$且$i-c_k \le k-1$
我们的首先我们肯定可以使用线段树来更新
但更进一步，对于这一类点，我们只需要在查询第一个点时使用线段树就可以了
因为这是一个前缀，之后$i$每向右移一位，合法的$j$也最多增加$1$
不难发现，总的暴力操作次数不大于左右区间中较小的一段
时间复杂度：$O(\log + \min(r-k+1,k-l))$
2. $g_i \le l$且$k-1 < i-c_k$
对于这些点，我们查询的是整个左区间
我们整体查一次，然后一起更新就可以了
时间复杂度：$O(\log n)$
3. $l < g_i < k$
对于这些点，我们查询的是左区间的一个后缀，我们直接在线段树上查就好
考虑所有会影响到$i$的$solve$，它们的左区间一定没有交集
也就是说只会有一个$solve$的左区间包含$g_i$
于是对于每一个$i$，在整个算法中只会被查询一次
所以这部分复杂度是$O(n \log n)$的，且不需要考虑到分治的复杂度中去
4. $g_i \le k$
直接不管就好

## 【HDU 5575】Discover Water Tank

### 解题报告

1. 区间水位低于$x$，那么我们分治$solve(l,x-1)+solve(x+1,r)$即可
2. 区间水位高于$x$，那么我们搞一个前缀和就好

## 【BZOJ 3237】[AHOI2013] 连通图

### Code

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 100000+9;
const int M = 1000000+9;
const int SGZ = 5;

int u[M],v[M],is_del[M],vout[N],idx;
int fa[N],n,m,k,sz[N],edg[N][SGZ];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Union_Find_Set{
#define UFS Union_Find_Set
int t1[M*5],t2[M*5],cnt;

inline int find(int w){
int f = fa[w], tmp;
while (fa[f] != f) f = fa[f];
while (w != f) t1[++cnt] = w, t2[cnt] = fa[w], fa[w] = f, w = t2[cnt];
return f;
}

inline void Union(int a, int b) {
int f1 = find(a), f2 = find(b);
if (f1 != f2) ++cnt, fa[t1[cnt]=t2[cnt]=f1] = f2;
}

inline void reset(int Tag) {
for (;cnt>Tag;cnt--)
fa[t1[cnt]] = t2[cnt];
}
};

void solve(int l, int r){
int cur_time = UFS::cnt;
if (l == r) {
vout[l] = 1;
for (int i=1,w;i<=sz[l] && vout[l];i++) {
w = edg[l][i];
if (UFS::find(u[w]) != UFS::find(v[w])) vout[l] = 0;
}
UFS::reset(cur_time);
} else {
int mid = l + r + 1 >> 1; ++idx;
for (int i=mid;i<=r;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
for (int i=l;i<mid;i++) for (int j=1,w;j<=sz[i];j++) {
w = edg[i][j];
if (is_del[w] != idx) UFS::Union(u[w],v[w]);
}
solve(mid,r);
UFS::reset(cur_time); ++idx;
for (int i=l;i<mid;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
for (int i=mid;i<=r;i++) for (int j=1,w;j<=sz[i];j++) {
w = edg[i][j];
if (is_del[w] != idx) UFS::Union(u[w],v[w]);
}
solve(l,mid-1);
UFS::reset(cur_time);
}
}

int main(){
for (int i=1;i<=n;i++) fa[i] = i;
for (int i=1;i<=k;i++) {
for (int j=sz[i];j;--j)
}
for (int i=1;i<=m;i++) if (~is_del[i]) UFS::Union(u[i],v[i]);
solve(1,k);
for (int i=1;i<=k;i++) puts(vout[i]?"Connected":"Disconnected");
return 0;
}

—————————— UPD 2017.2.1 ——————————

## 【BZOJ 2738】矩阵乘法

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 500+9;
const int M = 250000+9;
const int Q = 60000+9;

struct Point{int val,x,y;inline bool operator < (const Point &B) const {return val < B.val;}}p[M];
struct Query{int k,x1,x2,y1,y2,id;}q[Q],buf[Q];

int n,m,vout[Q];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

namespace Fenwick_Tree{
#define BIT Fenwick_Tree
#define lowbit(x) ((x)&-(x))
int sum[N][N];

inline void modify(int x, int y, int delta) {
if (x <= 0 || y <= 0) return;
for (int j=y;j<=n;j+=lowbit(j)) for (int i=x;i<=n;i+=lowbit(i))
sum[i][j] += delta;
}

inline int query(int x, int y){
if (x <= 0 || y <= 0) return 0;
int ret = 0;
for (int j=y;j;j-=lowbit(j)) for (int i=x;i;i-=lowbit(i))
ret += sum[i][j];
return ret;
}
};

void solve(int l, int r, int L, int R) {
if (l == r) for (int i=L;i<=R;i++) vout[q[i].id] = p[l].val;
else {
int mid = l + r + 1 >> 1,ls=L-1,rs=R+1;
for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,1);
for (int i=L,tmp;i<=R;i++) {
tmp = BIT::query(q[i].x1-1,q[i].y1-1);
tmp += BIT::query(q[i].x2,q[i].y2);
tmp -= BIT::query(q[i].x1-1,q[i].y2);
tmp -= BIT::query(q[i].x2,q[i].y1-1);
if (tmp >= q[i].k) buf[++ls] = q[i];
else q[i].k -= tmp, buf[--rs] = q[i];
}
memcpy(q+L,buf+L,sizeof(buf[0])*(R-L+1));
for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,-1);
if (L <= ls) solve(l,mid-1,L,ls);
if (rs <= R) solve(mid,r,rs,R);
}
}

int main(){
for (int j=1,t=1;j<=n;j++) for (int i=1;i<=n;i++,t++)
p[t].x = i, p[t].y = j, p[t].val = read();
for (int i=1,a,b,c,d,e,f;i<=m;i++)
q[i].k = read(), q[i].id = i;
sort(p+1,p+1+n*n);
solve(1,n*n,1,m);
for (int i=1;i<=m;i++) printf("%d\n",vout[i]);
return 0;
}

## 【BZOJ 4519】[Cqoi2016] 不同的最小割

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;

int n,m,vout[N*N],cnt,id[N],dis[N],pur,T=1;
queue<int> que;

inline void Add_Edge(int u, int v, int w) {
to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = w;
}

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

inline bool BFS(int s, int t) {
memset(dis,-1,sizeof(dis));
que.push(s); dis[s] = 0;

while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]])
dis[to[i]] = dis[w] + 1, que.push(to[i]);
}
return ~dis[t];
}

int DFS(int w, int f) {
if (w == pur) return f;
else {
int ret = 0;
for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
int tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
ret += tmp; f -= tmp; if (!f) return ret;
}
return ret;
}
}

inline int Dinic(int s, int t){
int ret = 0; pur = t;
while (BFS(s,t)) {
ret += DFS(s,INF);
} return ret;
}

void SIGN(int w) {
dis[w] = 1;
if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}

void solve(int l , int r){
if (l >= r) return ;
static int tmp[N]; int L=l-1, R=r+1;

for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
vout[++cnt] = Dinic(id[l],id[r]);

memset(dis,-1,sizeof(dis)); SIGN(id[l]);
for (int i=l;i<=r;i++)
if (~dis[id[i]]) tmp[++L] = id[i];
else tmp[--R] = id[i];
for (int i=l;i<=r;i++) id[i] = tmp[i];
solve(l,L); solve(R,r);
}

int main(){