【TopCoder SRM714】NAddOdd

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14408&rd=16883
神犇题解:http://codeforces.com/blog/entry/50602?#comment-358475

解题报告

设$f(x)=\sum\limits_{i=1}^{x}{g(k+i)}$
那么奇偶讨论,可以得到递推式$f(x)=(f(\frac{x-k}{2})+\frac{x}{2})+(f(\frac{x}{2})+x)$
于是递归算$f(\frac{x-k}{2})$,$\sum\limits_{i=\frac{x-k}{2}+1}^{\frac{x}{2}}{g(i)}$暴力算
时间复杂度:$O(k \log^2 n)$

Code

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

class NAddOdd {
    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] 影魔

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4826
神犇题解:http://www.cnblogs.com/Enceladus/p/6735887.html

解题报告

这题建出笛卡尔树,之后就是区间加、区间询问
于是将询问离线,用线段树维护一下就好了
总时间复杂度:$O(n \log n)$

至于笛卡尔树那一块,我们可以看作一个分治
而与最大值相关的题,分治是常见解法
所以这题还是很容易想到的吧

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;}
   
inline int read() {
    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() {
    n = read(); m = read();
    p1 = read(); p2 = read();
    for (int i=1;i<=n;i++) {
        val[i] = read();
    }
    ST.init(val); 
    solve(0, n+1); 
    for (int i=1;i<=m;i++) {
        q[i].l = read(); 
        q[i].r = read();
        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 3917】[Baltic2014] sequence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3917
神犇题解Ⅰ:http://blog.csdn.net/lcrtest/article/details/51312981
神犇题解Ⅱ:http://blog.csdn.net/neither_nor/article/details/52604754

吐槽

他们说这题是APIO 2016练习赛的题目,为什么我一点印象都没有 QwQ
想了很久都只会$O(\frac{n^2}{64})$的暴力,我也很绝望啊…..

解题报告

我们发现,对于比较高的位数来讲,其一样的数在一起
考虑将一样的数合在一起,并且从低位到高位处理

记录二进制状态$f_{i,j}$表示在第$i$位的时候,第$j$块里需要哪些数
如果当前只需要一个数了,那么就可以直接返回辣!(如果是0需要特判)
否则的话,我们枚举这一位在第一个数中是多少
因为下一层中连续的区间长度大概都比现在这一位连续的区间长10倍
所以我们可以把这一位中的状态每十个合成一块,下一层的话又是一个递归子问题,我们可以递归下去
考虑每一层的总复杂度:第$i$层有$10^i$个分叉,每个分叉内有$\frac{n}{10^i}$个块,于是每一层的复杂度是$O(n)$的
下面我们来总复杂度$T(n)=10 \cdot T(\frac{n}{10}) + n$
根据主定理,这货是$O(n \log{n})$的

【BZOJ 3897】Power

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3897
神犇题解:http://blog.csdn.net/jiangyuze831/article/details/44701467

解题报告

我们考虑给定一个区间$[l,r]$的起始体力值和最终体力值
那么显然我们应该把尽量多的体力值分配到收益最大的那一天$i$
然后$(i,r]$那一部分成了递归子问题,直接分治下去就可以了

至于前面那一部分,如果一直蓄力都不会满,那么就一直蓄力
否则的话,假设从第$j$天开始蓄力会满掉那么我们递归$[l,j-1]$即可
于是我们撸一发分治就可以了,时间复杂度:$O(n)$

【BZOJ 3711】[PA2014] Druzyny

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3711
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4654215.html
神犇题解Ⅱ:http://blog.csdn.net/u010600261/article/details/54917569

解题报告

去膜了题解,好神啊!
本题一个区间要同时受$c_i,d_i$的限制

于是我们先只考虑$d_i$的限制
那么对于某一个区间的右端点$i$来讲,设合法的左端点$\in [g_i,i)$
至于$g_i$怎么求?搞一个队列就可以了?或者二分也是可以的
另外还需要注意一点:$g_i$是单调递增的

现在我们再来考虑$c_i$的限制,我们使用分治来解决
在$solve(l,r)$的时候,我们找出$c_i$最大的那个点$k$,然后递归下去
在合并上来的时候,我们就只需要考虑$[l,k-1]$对于$[k,r]$的贡献了
更进一步:因为$c_k$是$[l,r]$中最大的那个,所以对于此时所有的转移,$c_i$的限制均只需要考虑$c_k$
那么此时对于$i \in [k,r]$来讲,其合法的左端点$j \in [max(l,g_i),min(k-1,i-c_k)]$
因为$g_i$单调递增,所以我们对于$[k,r]$从左到右分四段考虑:

  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$
    直接不管就好

现在我们来分析分治的复杂度:$T(a+b)=T(a)+T(b)+min(a,b)+\log n$
我们发现这和启发式合并一样,于是复杂度是$O(n \log n)$的
在算上第三类更新的复杂度,总时间复杂度仍然为$O(n \log n)$

值得一提的是,这种与最值相关的问题使用分治来解决已经多次出现
比如HDU 5575,一定要引起重视啊

【日常小测】巡游计划

题目大意

有$n(n \le 52501)$个城市,依次分布在数轴上
若你到达$i$号城市,则你必须停留$a_i$个单位时间
若你当前在$i$号城市,则你只能前往编号$\in (i,i+k]$的城市
若你在城市$i$,打算前往城市$j$,那么你会花费$|p_i-p_j| \cdot b_i$的时间
现在你从$1$号城市出发,最终到达$n$号城市,问花费的最短时间

解题报告

下面内容建立在你已经会了BZOJ 1492的维护凸壳的做法

先不考虑那个绝对值的限制,显然就是一个斜率DP的形式
我们考虑对序列建一个线段树,每一次得到了$i$号城市的答案后
我们在线段树上进行依次区间加的操作,即将$i$号城市对应的点加入线段树对应结点的凸壳内
因为在线段树上只会被拆分成$O(\log n)$个结点、插入凸壳复杂度$O(\log n)$,于是复杂度为$O(n \log^2 n)$

至于如何查询?我们从左到右依次处理,假设我们当前想得到$i$号城市的答案
那我们在$i$在线段树内对应的节点到根的路径上的每一个凸壳我们都询问一次答案
然后取一个最值就可以了,时间复杂度仍然是$O(n \log^2 n)$的

现在我们考虑绝对值的限制
我们可以钦定$p_i$与$p_j$的大小关系
具体来说,我们在得到$i$号城市的答案后,我们只是将他扔到线段树上去,但先不建立凸包
然后我们对那棵线段树进行中序遍历,那么在走到结点i的时候,我们已经知道了需要查询哪些点,凸壳总共有哪些点
于是我们将这些东西扔到一起,然后排序,然后从小到大遍历一次

如果是查询的点,就到当前的凸壳中更新答案
如果是应该加入到凸壳的点,那就加入到凸壳中
因为已经排过序,所以绝对值可以打开

我们再从大到小再来一遍,这样就可以得到这个结点的所有答案了
不难发现一个点只会被插入凸壳$O(\log n)$次,也只会被查询这么多次
所以时间复杂度仍然为$O(n \log^2 n)$

【HDU 5575】Discover Water Tank

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5575
神犇题解:http://blog.csdn.net/qq_19592437/article/details/50252111
中文题面:https://ly.men.ci/problem/199

解题报告

这题我们可以用左偏树+并查集什么的
不过感觉分治更好写吧?

考虑$solve(l,r)$表示区间$(l,r]$的最优解
那么找出其中最高的挡板设为$x$,之后分两种情况讨论

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

总的时间复杂度:$O(n \log n)$

【BZOJ 4237】稻草人

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4237
神犇题解:http://blog.csdn.net/lqybzx/article/details/51784992

解题报告

这题一年前就考过,当时连$O(n^2)$的容斥都不会 QwQ
当时知道std是分治的时候,眼珠子都快掉出来了
现在来看的话,因为做过BZOJ 4456,所以还是勉强能想出来?

考虑对y轴分治,这样每一次就只需要考虑跨过分治线的所有矩形了
这样的话,我们枚举合法矩形的右上端点,合法的左下端点的纵坐标就是单调下降的了
于是维护一个单调栈什么的就可以啦!

【BZOJ 2001】[HNOI2010] City 城市建设

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2001
神犇题解Ⅰ:http://www.cnblogs.com/BLADEVIL/p/3512644.html
神犇题解Ⅱ:http://blog.miskcoo.com/2015/04/bzoj-2001

解题报告

如果没有边权,只需要维护连通性
那么搞一个可以撤销的并查集就可以啦!

现在考虑带边权的情况,我们仍然对时间进行分治
在每一层,我们进行两个操作:

1. Contraction 缩小点的规模

将所有当前分治区间内会被修改的边的边权置为 $-INF$
然后做一遍MST,将此时通过非 $-INF$ 连接的点用并查集缩起来
因为$-INF$边只会有区间长度个,所以每一次分治后,点的规模不会超过分治区间的长度

2. Reduction 缩小边的规模

将会被修改的边的边权置为 $INF$,然后再做一遍MST
将此时不在MST中的边删去,因为保留的边数不会超过点数,所以边的规模也不会超过分治区间的长度

所以时间复杂度写出来长这样: $T(n) = 2T(\frac{n}{2}) + n\log n$
用主定理化简之后,时间复杂度就是: $O(n{\log ^2}n)$

【BZOJ 4456】[ZJOI2016] 旅行者

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4456
神犇题解:http://blog.csdn.net/neither_nor/article/details/51733997

解题报告

将询问离线后考虑分治
不停地将区间尽量划分成正方形
考虑每一个块内的询问:

1. 最优路径经过中轴线

那么我们枚举中轴线上的每一个点
跑一遍到块内所有点的最短路
然后用这个东西来更新答案

2. 最优路径不经过中轴线

那么我们递归处理

于是我们就在 $O(n\sqrt n {\log ^2}n)$ 的时间复杂度内解决这个问题了
然而复杂度可以被证明到少个 $log$ 参见:http://blog.csdn.net/neither_nor/article/details/51733997

【BZOJ 4059】[Cerc2012] Non-boring sequences

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4059
神犇题解Ⅰ:http://blog.csdn.net/popoqqq/article/details/46380617
神犇题解Ⅱ:http://krydom.com/bzoj4059/

解题报告

考虑直接找出所有不无聊的区间
直接 $ O(n^2)$ 枚举的话,会T掉,于是考虑分治
假如当前考虑到的区间为(l,r),且这个区间中一个只出现过一次的数为x,下标为p
那么显然,横跨x的区间合法,两边的区间就递归下去做就好啦!

但如果每一次我们从左到右扫描x的话,时间复杂度长这样:$ T(n) = T(n – 1) + n$
这样的话,上限是 $ O(n^2)$ 显然不清真
考虑同时从两边开始扫描的话,复杂度就变为了: $ T(n) = T(p) + T(n – p) + \min (n – p,p)$
于是这个是:$ O(n\log n)$ 的,于是就可以愉快的暴力啦!
至于复杂度的证明的话,我们发现这货的形式和线段树的启发式合并的式子长得一毛一样
因为线段树的启发式合并是 $ O(n\log n)$ 的,那么这货的复杂度也就是对的啦!

当然你也可以使用归纳法什么的来证明复杂度
甚至你可以根本不用这个暴力的算法,而使用优雅的矩形面积并来做:
http://www.cnblogs.com/DaD3zZ-Beyonder/p/5803964.html