bzoj 3821: 玄学

题目大意

有一个长度为 n 数列,有若干个事件,事件分为操作和询问两种,

一次操作是把数列[l...r] 区间中的每个元素x变成 ax + b mod p。

一次询问是询问 执行了 第l 次到第r次操作后第 k 个元素的值。

解题思路

标解是树套树,且平衡树一层需要写可持久化AVL来卡常。

松爷在考场上给出了一种编程复杂度更低的算法。

单独维护a,b两个系数,我们发现在这道题中的操作是支持结合律的,也就是说我们可以把一段操作后产生的效果提前预处理出来。

考虑用线段树维护把每一段区间操作执行后每一个元素的a和b的值。

等等。。每一个元素?那样的话岂不是要存下 线段树节点个数 * 序列中节点个数 个, 即 n^2 个点了吗?

但是这些点中很多个点的a和b值都是相同的, 很显然的一点是对于一个长度为L的区间, a,b值不同的段数是 O(L) 的。

所以说只要依次存下这L段的位置和a,b的值就可以了。 询问的时候需要先二分确定一下 k 这个数处于哪一段中。

具体实现的时候,因为包含r的区间一定只有在 r操作 出现后才会被询问到,所以说每一次插入的时候只要合并掉所有 R == p 的区间就可以了, 而每个区间只会被更新一次(即区间最右端点被插入的时候),所以复杂度得到保证。

加入操作复杂度为 O(logn), 询问操作复杂度 O(log2n) 。

技巧总结

要挖掘操作自身的一些性质, 并且选用合适的数据结构进行维护。 比如说支持合并操作的就可以用线段树啦

代码

写得丑死了QAQ

听了题目描述一个longlong都没有用炸了好久QAQ

作死地用了vector速度慢得飞起QAQ

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #define MAXN 200005
 8 #define MAXT 2500005
 9 #define pb push_back
10 using namespace std;
11 int read(){
12     int x=0,f=1;char ch=getchar();
13     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
14     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
15     return x*f;
16 }
17 vector <int> xx[MAXT], aa[MAXT], bb[MAXT];
18 int Q, tt, n, mod, num[MAXN], lastans, cntj, l, r, a, b, k;
19 long long A, B;
20 void jiemi(int &x){x ^= lastans;}
21 inline void update(int t){
22     int zuo = t + t, zz = 0, you = t + t + 1, yy = 0;
23     int sz = xx[zuo].size()-1, sy = xx[you].size()-1;
24     while(1){
25         xx[t].pb(max(xx[zuo][zz], xx[you][yy]));
26         aa[t].pb((long long)aa[zuo][zz]*aa[you][yy] % mod);
27         bb[t].pb(((long long)bb[zuo][zz]*aa[you][yy] % mod + bb[you][yy]) % mod);
28         if(zz == sz && yy == sy) break;
29         if((zz<sz) && ((yy == sy) || xx[zuo][zz+1] < xx[you][yy+1])) zz ++;
30         else if((yy<sy) && ((zz==sz) || xx[you][yy+1] < xx[zuo][zz+1])) yy ++;
31         else zz ++, yy ++;
32     }
33 }
34 void insert(int t, int l, int r, int L, int R, int p){
35     if(l == r){
36         if(L != 1){xx[t].pb(1); aa[t].pb(1); bb[t].pb(0);}
37         xx[t].pb(L); aa[t].pb(a); bb[t].pb(b);
38         if(R != n){xx[t].pb(R+1); aa[t].pb(1); bb[t].pb(0);}
39         return;
40     }
41     int mid = l + r >> 1;
42     if(mid >= p) insert(t + t, l, mid, L, R, p);
43     else insert(t + t + 1, mid + 1, r, L, R, p);
44     if(p == r) update(t);
45 }
46 inline int erfen(int t, int l, int r, int p){
47     while(l + 1 < r){
48         int mid = l + r >> 1;
49         if(xx[t][mid] <= p) l = mid;
50         else r = mid-1;
51     }if(xx[t][r] <= p) return r; return l;
52 }
53 inline void ask(int t, int p){
54     int x = erfen(t, 0, xx[t].size()-1, p);
55     A = (A*aa[t][x]) % mod; B = (B*aa[t][x]%mod+bb[t][x]) % mod;
56 }
57 void query(int t, int l, int r, int L, int R, int p){
58     if(l >= L && r <= R){ask(t, p); return;}
59     int mid = l + r >> 1;
60     if(L <= mid)query(t + t, l, mid, L, R, p);
61     if(R >= mid+1)query(t + t + 1, mid + 1, r, L, R, p);
62 }
63 int main(){
64     scanf("%d%d%d", &tt, &n, &mod);
65     for(int i = 1; i <= n; i ++) num[i] = read();
66     scanf("%d", &Q);
67     for(int qq = 1; qq <= Q; qq ++){
68         int cmd; cmd = read();
69         if(cmd == 1){
70             l = read(); r = read(); a = read(); b = read();
71             if(tt % 2 == 1) jiemi(l), jiemi(r);
72             insert(1, 1, Q, l, r, ++ cntj);
73         }else{
74             l = read(); r = read(); k = read();
75             if(tt % 2 == 1) jiemi(l), jiemi(r), jiemi(k);
76             A = 1; B = 0;
77             query(1, 1, Q, l, r, k);
78             lastans = (A*num[k]%mod+B) % mod;
79             printf("%d\n", lastans);
80         }
81     }
82 //    system("pause");
83     return 0;
84 }

时间: 11-23

bzoj 3821: 玄学的相关文章

BZOJ 2654 &amp; 玄学二分+MST

题意: 给一张图,边带权且带颜色黑白,求出一棵至少包含k条白边的MST SOL: 正常人都想优先加黑边或者是白边,我也是这么想的...你看先用白边搞一棵k条边的MST...然后维护比较黑边跟白边像堆一样慢慢往里面加...不过讲课的时候跟原题有点出入...这里只有k条边好像比较难维护... 正解也非常巧妙...首先如果有一棵MST,他所含白边数量多于k,那么我们如果可以适当增加白边的边权那么我们就可以减少它的边而且达到最优....想想很有道理你让我证明那有点日了狗了... 然后我们就二分白边的增加

BZOJ 1013: [JSOI2008]球形空间产生器sphere

二次联通门 : BZOJ 1013: [JSOI2008]球形空间产生器sphere /* BZOJ 1013: [JSOI2008]球形空间产生器sphere 高斯消元 QAQ SB的我也能终于能秒题了啊 设球心的坐标为(x,y,z...) 那么就可以列n+1个方程,化化式子高斯消元即可 */ #include <cstdio> #include <iostream> #include <cstring> #define rg register #define Max

bzoj 3309 DZY Loves Math - 莫比乌斯反演 - 线性筛

对于正整数n,定义f(n)为n所含质因子的最大幂指数.例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0. 给定正整数a,b,求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b). Input 第一行一个数T,表示询问数. 接下来T行,每行两个数a,b,表示一个询问. Output 对于每一个询问,输出一行一个非负整数作为回答. Sample Input 4 7558588 9653114 6514903 445

【BZOJ】[HNOI2009]有趣的数列

[算法]Catalan数 [题解] 学了卡特兰数就会啦>_<! 因为奇偶各自递增,所以确定了奇偶各自的数字后排列唯一. 那么就是给2n个数分奇偶了,是不是有点像入栈出栈序呢. 将做偶数标为-1,做奇数标为+1,显然当偶数多于奇数时不合法,因为它压不住后面的奇数. 然后其实这种题目,打表就可知啦--QAQ 然后问题就是求1/(n+1)*C(2n,n)%p了,p不一定是素数. 参考bzoj礼物的解法. 看到网上清一色的素数筛+分解质因数解法,不解了好久,感觉写了假的礼物-- 后来觉得礼物的做法才比

洛谷 P2709 BZOJ 3781 小B的询问

题目描述 小B有一个序列,包含N个1~K之间的整数.他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数.小B请你帮助他回答询问. 输入输出格式 输入格式: 第一行,三个整数N.M.K. 第二行,N个整数,表示小B的序列. 接下来的M行,每行两个整数L.R. 输出格式: M行,每行一个整数,其中第i行的整数表示第i个询问的答案. 输入输出样例 输入样例#1: 6 4 3 1 3 2 1 1 3

BZOJ 1012: [JSOI2008]最大数maxnumber(线段树)

012: [JSOI2008]最大数maxnumber Time Limit: 3 Sec  Memory Limit: 162 MB Description 现在请求你维护一个数列,要求提供以下两种操作:1. 查询操作.语法:Q L 功能:查询当前数列中末尾L个数中的最大的数,并输出这个数的值.限制:L不超过当前数列的长度.2. 插入操作.语法:A n 功能:将n加上t,其中t是最近一次查询操作的答案(如果还未执行过查询操作,则t=0),并将所得结果对一个固定的常数D取模,将所得答案插入到数列

【BZOJ】【1016】【JSOI2008】最小生成树计数

Kruskal/并查集+枚举 唉我还是too naive,orz Hzwer 一开始我是想:最小生成树删掉一条边,再加上一条边仍是最小生成树,那么这两条边权值必须相等,但我也可以去掉两条权值为1和3的,再加上权值为2和2的,不也满足题意吗?事实上,如果这样的话……最小生成树应该是1和2,而不是1和3或2和2!!! 所以呢?所以对于一个图来说,最小生成树有几条边权为多少的边,都是固定的!所以我们可以做一遍Kruskal找出这些边权,以及每种边权出现的次数.然后,对于每种边权,比方说出现了$v_i$

【BZOJ】【2844】albus就是要第一个出场

高斯消元解XOR方程组 srO  ZYF  Orz 膜拜ZYF…… http://www.cnblogs.com/zyfzyf/p/4232100.html 1 /************************************************************** 2 Problem: 2844 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:252 ms 7 Memory:2052 kb 8 *******

[BZOJ 1066] [SCOI2007] 蜥蜴 【最大流】

题目链接:BZOJ - 1066 题目分析 题目限制了高度为 x 的石柱最多可以有 x 只蜥蜴从上面跳起,那么就可以用网络流中的边的容量来限制.我们把每个石柱看作一个点,每个点拆成 i1, i2,从 i1 到 i2 连一条边,容量为这个石柱 i 的高度,即跳跃次数限制.来到这个石柱就是向 i1 连边,从这个石柱跳起就是从 i2 向外连边,这样只要从石柱 i 跳起就一定会消耗 i1 到 i2 的边的容量.如果 i 有蜥蜴,就从 S 到 i1 连一条容量为 1 的边,如果从石柱 i 能跳出边界,就从