https://ac.nowcoder.com/acm/problem/15815   首先暴力枚举每一个区间必定是超时的。那么考虑每个点对于答案的贡献值，可以这样想，对于点h[i]作为最大值在多少个区间出现，作为最小值在多少个区间出现？这个点对于答案的贡献就是h[i]*作为最大值出现的次数 - h[i]*作为最小值出现的次数，对于每个点，求一下贡献累加即可。 求每个点贡献的过程用单调栈来维护，拿求最大值的次数来举例。对于点i，找到左端第一个比h[i]大的数，记其位置为L，找到右端第一个比h[i]大的数，记其位置为…

草，不会做啊不会做啊不会做啊…… 题意: 维护一个长度为n的正整数序列a_1,a_2,...,a_n，支持以下两种操作： 1 k，将序列a从小到大排序，输出a_k的值。 2 k，将所有严格大于k的数a_i减去k。 sol: 平衡树，大家都会，减掉 \(k\) 后，相对位置发生改变的，只有 \([1,k]\) 和 \([k+1,2k]\)。 我们发现这个减法，如果减成功了，不会超过 \(\log\) 次的。 所以复杂度是 \(n \log^2 n\)，大概是和启发式合并一样>_<。 具体点的做法大概就是，…

如题。在补题解ing。 觉得放代码可能会卡死，考虑到这个，这一篇就不放代码了。 edu 41 E 显然是主席树，枚举一个 \(j\) 然后找一下 \(1 ~ a_j\) 这段区间有多少个大于等于 \(j\) 的，就做完了吧，答案记得除掉2。 F 这个显然是 \(border\) 吧，然后我们考虑用哈希快速判断两个串是否相等。 倒着枚举，你会发现每次最多增长2，如果没有增长的话直接往下减，复杂度易证。 G 斯特林数，会了再更。 edu 42 E 性质题，有空做。 F 一个连通块是一个环，点数 = 边数。所以我们找一下…

题 1.插入x 2.删除x 3.给s,查询\(a\&s==a\)的个数 插入和删除其实是相同的。 插入删除的时候前八位枚举子集，操作一下就行了。 查询的时候枚举后八位，然后就高维前缀和一下输出即可。 #include<bits/stdc++.h> #define rep(i,x,y) for(int i=x;i<=y;i++) using namespace std; void cmax(int&x,const int&y){x=x>y?x:y;} void cmin…

简单数据结构题？ 我们先考虑一个朴素分治。 \([l, mid]\) 和 \([mid + 1, r]\) 递归求解。 \([l,r]\) 的区间需要通过 \([l, mid]\) 的后缀和 \([mid+1,r]\) 的前缀来求解。 第一次枚举前者的后缀然后移动后者，第二次枚举后者然后移动前者。 这样的复杂度是 \(n \log n\) 但是只能支持一次询问（bushi）。 但是我们发现由于 \(OR\) 的性质，不会变化超过 \(\log\) 次。所以我们考虑线段树在每个节点记录一下是哪些位置让这个发生了改变。…

#{} 表示占位符(预编译) #{}相当于jdbc中的preparedstatement，可以防止sql注入攻击   parameterType="map"                              #{}里面写的是map的key parameterType="cn.pojo.Object"              #{}里面写的是实体类中的属性 parameterType="int"(等数据类型)             #{}里面随意写   ${}表示拼接 直接输出属性的值 MyBatis排序…