# bzoj 3821: 玄学

### 代码

``` 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;
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){
71             if(tt % 2 == 1) jiemi(l), jiemi(r);
72             insert(1, 1, Q, l, r, ++ cntj);
73         }else{
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 }```

## 【BZOJ】[HNOI2009]有趣的数列

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

## 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\$