【BZOJ 4785】[ZJOI 2017] 树状数组

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4785
出题人传送门:http://jiruyi910387714.is-programmer.com/posts/209073.html
官方题解:https://pan.baidu.com/s/1dFGHFfr

解题报告

我们发现正常的代码是统计的前缀和
但劼的写法实际是统计后缀和
然后画一画发现,只有$l-1,r$这两个点被改到的时候才会影响答案

我们考虑询问区间是$[l,r]$,一个修改区间是$[a,b]$
那么如果$l,r \in [a,b]$则这个修改区间有$\frac{2}{b-a+1}$的可能影响到答案
如果$l,r$只有一个$\in [a,b]$那么这个修改区间有$\frac{1}{b-a+1}$的可能影响到答案
如果两个都不属于,其显然不会影响到答案

于是我们把修改操作看成二维平面上的点的话
每一个询问操作可以拆成三个矩阵的询问
这个是经典问题,可以用树套树/分治/K-d Tree来解决

至于怎么维护标记,直接做的话,我们可以看成矩阵乘法
因为这个转移矩阵非常特殊,搞一搞发现其不但满足结合律,还满足交换律,所以可以标记永久化
但还有更妙的做法:

我们可以搞一个类似生成函数的东西
设第$i$个操作有$p_i$的可能影响到当前询问,设两个端点被改变偶数次的概率为$a$,奇数次为$b$
那么最后$a-b=\prod\limits_{i}{(1-p_i)-p_i}$
为什么是对的呢?因为只有改变奇数次才会为奇数,而$-1$的奇数次方等于$-1$偶数次方等于$1$,所以刚好对上
又因为我们还知道$a+b=1$,所以$a = \frac{1+\prod\limits_{i}{(1-p_i)-p_i}}{2}$

另外的话,这题有一个坑点:如果$l-1=0$的话,我们需要特判
因为之前我们的推导基于$l-1$那个点记录的是一个后缀
而实际算法中我们我们默认$l-1$那个点的值为$0$,所以需要判断一下总操作次数奇偶
考试的时候就这一点没想到,血wa三小时,最后这题挂零

Code

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

const int N = 100009;
const int M = 30000000;
const int MOD = 998244353;
const int REV = 499122177;

inline int read() {
	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;
}

int n,m,tot;
class Segment_Tree{
	int cnt,root,AnsTmp,ch[M][2],prod[M][2];
	public:
		inline void modify(int x, int y, int v, bool t) {
			modify(root, 1, n, x, y, v, t);
		}
		inline int query(int x1, int x2, int y1, int y2, bool t) {
			if (x1 > x2 || y1 > y2) return 1;
			AnsTmp = 1;
			query(root, 1, n, x1, x2, y1, y2, t);
			return (AnsTmp+MOD)%MOD;
		}
	private:
		void modify(int &w, int l, int r, int x, int y, int v, bool t) { //X
			if (!w) w = ++cnt; modify(prod[w][0], 1, n, y, v, t);
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (x < mid) modify(ch[w][0], l, mid-1, x, y, v, t);
				else modify(ch[w][1], mid, r, x, y, v, t); 
			}
		}
		void modify(int &w, int l, int r, int p, int v, bool t) { //Y
			if (!w) w = ++cnt, prod[w][0] = prod[w][1] = 1; 
			prod[w][t] = (LL)prod[w][t] * v % MOD;
			if (l < r) {
				int mid = l + r + 1 >> 1;
				if (p < mid) modify(ch[w][0], l, mid-1, p, v, t);
				else modify(ch[w][1], mid, r, p, v, t);
			}
		}
		void query(int w, int l, int r, int L, int R, int y1, int y2, bool t) { //X
			if (!w) return;
			if (L <= l && r <= R) query(prod[w][0], 1, n, y1, y2, t);
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, y1, y2, t);
				if (mid <= R) query(ch[w][1], mid, r, L, R, y1, y2, t);
			}
		}
		void query(int w, int l, int r, int L, int R, bool t) { //Y
			if (!w) return;
			if (L <= l && r <= R) AnsTmp = (LL)AnsTmp * prod[w][t] % MOD;
			else {
				int mid = l + r + 1 >> 1;
				if (L < mid) query(ch[w][0], l, mid-1, L, R, t);
				if (mid <= R) query(ch[w][1], mid, r, L, R, t);
			}
		}
}SGT;

inline int Pow(int w, int t) {
	int ret = 1;
	for (;t;t>>=1,w=(LL)w*w%MOD)
		if (t&1) ret=(LL)ret*w%MOD;
	return ret;
}

int main() {
	n = read(); m = read();
	for (int i=1,l,r,len,ret;i<=m;i++) {
		if (read() == 1) {
			l = read(); r = read(); 
			len = Pow(r-l+1, MOD-2); ++tot;
			SGT.modify(l, r, (1 - (len * 2ll)) % MOD, 0);
			SGT.modify(l, r, (1 - (len * 4ll)) % MOD, 1);
		} else {
			l = read() - 1; r = read(); ret = 1;
			ret = (LL)ret * SGT.query(1, l, l, r - 1, 0) % MOD;
			ret = (LL)ret * SGT.query(l+1, r, r, n, 0) % MOD;
			ret = (LL)ret * SGT.query(1, l, r, n, 1) % MOD;
			ret = (ret + 1ll) * REV % MOD;
			if (!l&&(tot&1)) ret = (1 - ret) % MOD; 
			printf("%d\n",(ret+MOD)%MOD);
		}
	}
	return 0;
}

【日常小测】资源采集

题目大意

给定一棵$n(n \le 52501)$个点的树,初始状态下,每一结点存储的能量为$0$
树上每一个点有两个属性$v_i,l_i$分别表示这个点每单位时间产生的能量,和这个点的存储能量的上限
再给定$q(q\le52501)$个操作,每个操作有三个属性$w_i,d_i,t_i$,表示
在$t_i$的时刻,遍历在$w_i$的子树中且与$w_i$距离不超过$d_i$的点,并收集这些点的能量
一个点的能量被收集后就会清空,询问每次操作能够收集到多少能量

解题报告

先来说一说链上的情况,我们定义$last_i$为$i$号点上一次被收集的时间
我们可以把相邻的且$last_i$相同的点合并在一起,然后询问的时候用函数式线段树来回答
如果还有什么问题的话,我们可以戳这个题:市场

现在考虑树上的情况,我们先搞出DFS序,将其作为一个点的横坐标
然后我们把深度作为这个点的纵坐标,然后把这个点扔到平面上
这样单次操作就是对于一个平面上的矩形进行操作
这个是经典的$Kd-Tree$的应用,可以做到单次操作只影响到$\sqrt{n}$个结点
于是将$Kd-Tree$子树中$last_i$相同的点合在一起,打一个标记
单次操作最多增加$\sqrt n$个标记,而每一次在$Kd-Tree$上走一次就会回收一个标记
于是总的操作次数为$q\sqrt n$的
当然我们也需要用平衡树的启发式合并,或者函数式线段树来支持询问
于是总的时间复杂度为:$O(q \sqrt n \log n)$

不过众所周知,这题的暴力是$O(nq)$的
所以非递归的暴力跑得飞快,两秒的题目暴力可以卡到一秒以内
所以考完改题的时候,所有改了的人都是用的暴力……

【日常小测】传送门

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/438964732567423.png
官方题解:http://paste.ubuntu.com/24129177/

解题报告

这题当然可以用二维线段树做
不过显然KD-Tree更好写

但考场上T了两个点
加上一个如果子树最优解大于已知答案就不进入的剪枝后速度就成Rank 1了 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 200009;
 
int n,vout,itr[N];
struct Point{int x,y,a,b,mnx,mny,mxx,mxy,v,ori,ch[2];}p[N];
inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
inline bool cmp(const int a, const int b) {return p[a].x < p[b].x || (p[a].x == p[b].x && p[a].y < p[b].y);}
 
inline int read() {
    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;
}
 
class KD_Tree{
    int root,ans_tmp;
    public:
        inline void init() {
            n = read();
            for (int i=1;i<=n;i++) {
                p[i].mnx = p[i].mxx = p[i].x = read();
                p[i].mny = p[i].mxy = p[i].y = read();
                p[i].a = read(); p[i].b = read();
            }       
            build(root, 1, n, 0);
        }
        inline void insert(int id, int v) {
            insert(root, 1, n, id, v);
        }
        inline int query(int id) {
            ans_tmp = 0;
            query(root, 1, n, id, judge(id, root));
            return ans_tmp;         
        }
    private:
        void build(int &w, int l, int r, bool t) {
            if (l == r) w = l;
            else if (l < r) {
                int mid = l + r >> 1; w = mid;
                if (t) nth_element(p+l, p+mid, p+r+1, cmpx);
                else nth_element(p+l, p+mid, p+r+1, cmpy);
                build(p[w].ch[0], l, mid-1, t^1);
                build(p[w].ch[1], mid+1, r, t^1);
                for (int i=0,s;i<2;i++) if (s = p[w].ch[i]) {
                    p[w].mnx = min(p[s].mnx, p[w].mnx);
                    p[w].mny = min(p[s].mny, p[w].mny);
                    p[w].mxx = max(p[s].mxx, p[w].mxx);
                    p[w].mxy = max(p[s].mxy, p[w].mxy);
                }
            }
        }
        inline bool Contain(int w, int id) {
            if (!w) return 0;
            else return p[w].mnx <= p[id].x && p[id].x <= p[w].mxx && p[w].mny <= p[id].y && p[id].y <= p[w].mxy;
        }
        void insert(int w, int l, int r, int id, int v) {
            p[w].v = max(p[w].v, v);
            if (l < r) {
                int mid = l + r >> 1;
                if (Contain(p[w].ch[0], id)) insert(p[w].ch[0], l, mid-1, id, v);
                if (Contain(p[w].ch[1], id)) insert(p[w].ch[1], mid+1, r, id, v);
            }
        }
        inline int judge(int i, int j) {
            if (p[i].x <= p[j].mnx && p[i].y <= p[j].mny && p[j].mxx <= p[i].a && p[j].mxy <= p[i].b) return 2;
            else return max(p[i].x, p[j].mnx) <= min(p[i].a, p[j].mxx) && max(p[i].y , p[j].mny) <= min(p[i].b, p[j].mxy);
        }
        void query(int w, int l, int r, int id, int ty) {
            if (ty == 2) ans_tmp = max(ans_tmp, p[w].v);
            else {
                if (p[id].x <= p[w].x && p[w].x <= p[id].a && p[id].y <= p[w].y && p[w].y <= p[id].b) ans_tmp = max(ans_tmp, p[w].ori);
                int mid = l + r >> 1, tmp;
                if (p[w].ch[0] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[0]))) query(p[w].ch[0], l, mid-1, id, tmp);
                if (p[w].ch[1] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[1]))) query(p[w].ch[1], mid+1, r, id, tmp);
            }
        }
}kd;
 
int main() {
    kd.init();
    for (int i=1;i<=n;i++) itr[i] = i;
    sort(itr+1, itr+1+n, cmp);
    for (int j=n,v,i=itr[j];j;i=itr[--j]) {
        v = kd.query(i);
        kd.insert(i, ++v);
        p[i].ori = v;
        vout = max(v, vout);    
    }
    printf("%d\n",vout);
    return 0;
}

【BZOJ 4358】permu

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4358
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5049090.html
神犇题解Ⅱ:http://www.cnblogs.com/czllgzmzl/p/5644724.html

解题报告

1. 莫队+并查集

首先我们考虑一个简化版本:搞一个莫队,然后搞一个值域线段树
这样的话,我们的复杂度就是 $O({n^{1.5}}logn)$ 的,虽然可能会T,但很好想
现在考虑怎么把$log$去掉:如果莫队那里只存在插入操作,那么我们就可以使用并查集来维护
于是考虑莫队那里只有左端点的移动那里会有删除操作,于是我们每一次把左端点块内那一部分拿出来暴力重构
这样的话,复杂度就神奇地少了一个$log$!总复杂度: $O(n\sqrt n \alpha (n))$ 感觉可以A地样子!

2. KD-Tree

这里就是本题的高能部分!简直是太神啦!_(:з」∠)_
考虑将询问化为二维上的点,然后我们按照点值的大小,将序列的位置一个一个插入
每一次把所有包含他的询问的计数器加一,其他的询问的计数器置零
于是我们的每个询问对应的点上的计数器的历史最大值就是这个询问的答案啦!
时间复杂度:$O(n \sqrt n)$

【BZOJ 4520】[Cqoi2016] K远点对

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4520

这货我最开始写的是二分距离,查询用KD_Tree来查
然而这样的复杂度是没有保障的,于是光荣TLE
其实这货↑是写挂了,连30%的数据都没有拿到分 ←_←

然而这货的正解仍然是KD_Tree
最然感觉时间复杂度比较迷……
就是进入块中时,判断这个块是否能更新答案

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

const int N = 100000+9;

struct Point{int x,y;}p[N];
int n,k;
struct CMP{inline bool operator () (const LL A, const LL B){return A>B;}};
priority_queue<LL,vector<LL>,CMP> que; 

inline int read(){
	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 KD_Tree{
	#define KDT KD_Tree
	int MXx[N],MXy[N],MNx[N],MNy[N],ch[N][2],sz[N];
	int root,ans_tmp,P; LL LEN; 
	
	inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
	inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
	
	inline void update(int w){
		for (int i=0;i<=1;i++) if (ch[w][i]) {
			MXx[w] = max(MXx[w], MXx[ch[w][i]]);
			MXy[w] = max(MXy[w], MXy[ch[w][i]]);
			MNx[w] = min(MNx[w], MNx[ch[w][i]]);
			MNy[w] = min(MNy[w], MNy[ch[w][i]]);
			sz[w] += sz[ch[w][i]];
		}
	}
	
	int build(int l, int r, int ty) {
		int mid = l + r >> 1; sz[mid] = 1;
		if (ty) nth_element(p+l,p+mid,p+r+1,cmpx);
		else nth_element(p+l,p+mid,p+r+1,cmpy);
		MXx[mid] = MNx[mid] = p[mid].x;
		MXy[mid] = MNy[mid] = p[mid].y;
		
		if (l < mid) ch[mid][0] = build(l,mid-1,ty^1);
		if (mid < r) ch[mid][1] = build(mid+1,r,ty^1);
		update(mid); return mid; 
	}inline void build_Tree(){root = build(1,n,1);}
	
	#define Pow(x) ((LL)(x)*(x))
	#define DIS(p1,p2) (Pow(p[p1].x-p[p2].x)+Pow(p[p1].y-p[p2].y))
	
	inline LL judge(int w) {
		LL ret = 0;
		ret += max(Pow(MXx[w]-p[P].x), Pow(MNx[w]-p[P].x));
		ret += max(Pow(MXy[w]-p[P].y), Pow(MNy[w]-p[P].y));
		return ret;
	}
	
	void query(int w) {
		LL dw = DIS(w,P), dl = 0, dr = 0; 
		if (dw > que.top()) que.pop(), que.push(dw);
		if (ch[w][0]) dl = judge(ch[w][0]);
		if (ch[w][1]) dr = judge(ch[w][1]);
		
		if (dl > dr) {
			if (dl > que.top()) query(ch[w][0]);
			if (dr > que.top()) query(ch[w][1]);
		} else {
			if (dr > que.top()) query(ch[w][1]);
			if (dl > que.top()) query(ch[w][0]);
		} 
	} inline void Query(const int po){P = po;query(root);}	
};

int main(){
	n = read(); k = read();
	for (int i=1;i<=n;i++) p[i].x = read(), p[i].y = read();
	for (int i=1;i<=k*2;i++) que.push(0); KDT::build_Tree();
	for (int i=1;i<=n;i++) KDT::Query(i);
	printf("%lld\n",que.top());
	return 0;
}

貌似O(nk)的旋转卡壳也可以过?
貌似网上有一位很激动的同学说一条直线的时候没凸包?
感觉板子如果鲁棒一点的话,没有问题吧?