愿在线段树中搁浅
板子
非终版，后续会删改跟新润色
点修改，区间求和
#include <bits/stdc++.h>
const int maxn = 1e5+100;
using namespace std;
int a[maxn];
struct SegmentTree{
int l,r;
int sum;
}t[maxn*4];
void build(int o,int l,int r){
t[o].l=l,t[o].r=r;
if (l == r) {t[o].sum = a[l];return;}
int mid = (l+r)>>1;
build(o*2,l,mid),build(o*2+1,mid+1,r);
t[o].sum = t[o*2].sum+t[o*2+1].sum;
}
void update(int o,int x,int v){
if (t[o].l==t[o].r){t[o].sum += v;return;}
int mid = (t[o].l+t[o].r)>>1;
if (x <= mid) update(o*2,x,v);
else update(o*2+1,x,v);
t[o].sum=t[o*2].sum+t[o*2+1].sum;
}
int query(int o,int l,int r){
if (l<=t[o].l && r>=t[o].r) return t[o].sum;
int mid = (t[o].l+t[o].r) >> 1;
int sum=0;
if (l<=mid) sum+=query(o*2,l,r);
if (r>mid) sum+=query(o*2+1,l,r);
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n ;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
cin >> m;
for (int i=1;i<=m;i++){
int flag;
cin >> flag;
if (flag == 2){
int x,y;
cin >> x >> y;
cout << query(1,x,y) << endl;
}
if (flag == 1){
int x,y;
cin >> x >> y;
update(1,x,y);
}
}
}
区间修改，区间查询
#include <bits/stdc++.h>
const int maxn = 2*1e5+100;
#define LL long long
using namespace std;
int a[maxn];
struct SegmentTree{
int l,r;
LL sum,add;
}t[maxn*4];
void build(int o,int l,int r){
t[o].l=l,t[o].r=r;
if (l == r) {t[o].sum = a[l];return;}
int mid = (l+r)>>1;
build(o*2,l,mid),build(o*2+1,mid+1,r);
t[o].sum = t[o*2].sum+t[o*2+1].sum;
}
void maintain(int o){
if (t[o].add){
t[o*2].sum += t[o].add*(t[o*2].r-t[o*2].l+1);
t[o*2+1].sum += t[o].add*(t[o*2+1].r-t[o*2+1].l+1);
t[o*2].add += t[o].add;
t[o*2+1].add += t[o].add;
t[o].add = 0;
}
}
void update(int o,int l,int r,int d){
if (l<=t[o].l && r>= t[o].r){
t[o].sum += d*(t[o].r-t[o].l+1);
t[o].add += d;
return;
}
maintain(o);
int mid = (t[o].l+t[o].r)>>1;
if (l <= mid) update(o*2,l,r,d);
if (r>mid) update(o*2+1,l,r,d);
t[o].sum=t[o*2].sum+t[o*2+1].sum;
}
LL query(int o,int l,int r){
if (l<=t[o].l && r>=t[o].r) return t[o].sum;
maintain(o);
int mid = (t[o].l+t[o].r) >> 1;
LL sum=0;
if (l<=mid) sum+=query(o*2,l,r);
if (r>mid) sum+=query(o*2+1,l,r);
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n ;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
cin >> m;
for (int i=1;i<=m;i++){
int flag;
cin >> flag;
if (flag == 2){
int x,y;
cin >> x >> y;
cout << query(1,x,y) << endl;
}
if (flag == 1){
int x,y,z;
cin >> x >> y >> z;
update(1,x,y,z);
}
}
}
三种操作：
1.将某区间每一个数乘上x
2.将某区间每一个数加上x
3.求出某区间每一个数的和
#include <bits/stdc++.h>
const int maxn = 2*1e5+100;
#define LL long long
#define ls o*2
#define rs ls+1
using namespace std;
LL a[maxn],p;
struct SegmentTree{
int l,r;
LL sum,add,mul;
}t[maxn*4];
void build(int o,int l,int r){
t[o].l=l,t[o].r=r;t[o].mul=1;
if (l == r) {t[o].sum = a[l];return;}
int mid = (l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[o].sum = t[ls].sum+t[rs].sum;
}
void maintain(int o){
t[ls].sum = t[ls].sum*t[o].mul %p;
t[rs].sum = t[rs].sum*t[o].mul % p;
t[ls].sum += t[o].add*(t[ls].r-t[ls].l+1);
t[rs].sum += t[o].add*(t[rs].r-t[rs].l+1);
t[ls].mul = t[o].mul * t[ls].mul % p;
t[rs].mul = t[o].mul * t[rs].mul % p;
t[ls].add = t[o].mul *t[ls].add %p;
t[rs].add = t[o].mul * t[rs].add % p;
t[ls].add = (t[o].add +t[ls].add)%p;
t[rs].add = (t[o].add +t[rs].add)%p;
t[o].add = 0;
t[o].mul = 1;
}
void addf(int o,int l,int r,int d){
if (l<=t[o].l && r>= t[o].r){
t[o].sum += d*(t[o].r-t[o].l+1);
t[o].add += d;
return;
}
maintain(o);
int mid = (t[o].l+t[o].r)>>1;
if (l <= mid) addf(ls,l,r,d);
if (r>mid) addf(rs,l,r,d);
t[o].sum=t[ls].sum+t[rs].sum;
}
void mulf(int o,int l,int r,int d){
if (l<=t[o].l && r>= t[o].r){
t[o].sum = t[o].sum * d % p;
t[o].add = t[o].add * d % p;
t[o].mul = d * t[o].mul % p;
return;
}
maintain(o);
int mid = (t[o].l+t[o].r)>>1;
if (l <= mid) mulf(ls,l,r,d);
if (r>mid) mulf(rs,l,r,d);
t[o].sum=t[ls].sum+t[rs].sum;
}
LL query(int o,int l,int r){
if (l<=t[o].l && r>=t[o].r) return t[o].sum;
maintain(o);
int mid = (t[o].l+t[o].r) >> 1;
LL sum=0;
if (l<=mid) sum=(sum+query(ls,l,r))%p;
if (r>mid) sum=(query(rs,l,r)+sum)%p;
return sum;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,m;
cin >> n >> m >> p;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
for (int i=1;i<=m;i++){
int flag;
cin >> flag;
if (flag == 3){
int x,y;
cin >> x >> y;
cout << query(1,x,y) << endl;
}
if (flag == 2){
int x,y,z;
cin >> x >> y >> z;
addf(1,x,y,z);
}
if (flag == 1){
int x,y,z;
cin >> x >> y >> z;
mulf(1,x,y,z);
}
}
}
线段树上二分
线段树如果加上一个操作，询问在 [l,r]中第一个大于或小于某个数的位置
维护区间min,max 我们假设我们要找到 [l,r]中第一个小于 ll 的位置。
首先的，如果左儿子的最小值小于 ll，那么答案就在左边，不然的话再去右边搜，这样的话保证每个地方只会搜到一边，那么我们就用 O(nlogn)的复杂度解决了这个问题。
struct Segment_Tree {
int lc[N << 2], rc[N << 2], minn[N << 2];
void pushup(int u) {minn[u] = min(minn[u << 1], minn[u << 1 | 1]);}
void build(int u, int l, int r) {
lc[u] = l, rc[u] = r;
if(l == r) {
minn[u] = 0;
return;
}
build(u << 1, l, (l + r) >> 1), build(u << 1 | 1, (l + r >> 1) + 1, r);
pushup(u);
}
int search(int u, int l, int k) {
//Find the first element < k in [l, r]
if(lc[u] == rc[u]) {
if(minn[u] >= k) return -1;
return lc[u];
}
if(minn[u] >= k) return -1;
if(rc[u] < l) return -1;
int res = search(u << 1, l, k);
if(res != -1) return res;
return search(u << 1 | 1, l, k);
}
void update(int u, int p, int va) {
if(lc[u] == rc[u]) {
//cout << ' ' << lc[u] << ' ' << rc[u] << ' ' << u << endl;
minn[u] = va;
return;
}
if(p <= (lc[u] + rc[u] >> 1)) update(u << 1, p, va);
else update(u << 1 | 1, p, va);
pushup(u);
//cout << u << ' ' << lc[u] << ' ' << rc[u] << ' ' << minn[u] << endl;
}
}seg;
线段树例题
小鸡的排列构造的checker
题解：
区间里有多少个小于等于 p的数字？
于是我们可以维护一个初始全 0 的树状数组，按照 pi从小到大给树状数组的对应位置 +1
询问 [2,5,4]其实是在对状态4的数组求 [2,5] 区间的和，使用树状数组可以做到。
因此，像上述过程一样，把所有 [l,r,c]询问按照 p[c]从小到大排序，树状数组维护上述过程即可，复杂度 O(nlogn)
其它做法，例如主席树，不会
代码：
#include<bits/stdc++.h>
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define eps 1e-7
#define INF 0x3f3f3f3f
#define inf -2100000000
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxn = 3e5 + 10;
const double EPS = 1e-10;
const ll p = 1e7+9;
const ll mod = 1e9+7;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline int read(){
int ret=0,f=0;char ch=getchar();
while(ch>'9'||ch<'0') f^=ch=='-',ch=getchar();
while(ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
return f?-ret:ret;
}
struct node{
int l,r,val,id;
}b[maxn],a[maxn];
int ans[maxn],tree[maxn << 2];
bool cmp(node a, node b){
return a.val < b.val;
}
void push_up(int rt){
tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
}
void update(int p, int l, int r, int rt){
if(l == r){
tree[rt]++;
return ;
}
int mid = (l+r) >> 1;
if(p <= mid) update(p, lson);
else update(p, rson);
push_up(rt);
}
int query(int a,int b,int l,int r,int rt){
if(a<=l && r<=b){
return tree[rt];
}
int mid = (l+r) >> 1;
int ans = 0;
if(a <= mid) ans += query(a, b, lson);
if(b > mid)ans += query(a, b, rson);
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
cin>>_;
while(_--) {
int n,m;
cin >> n >> m;
memset(tree,0,sizeof(tree));
for(int i = 1; i <= n; i++){
cin >> a[i].val;
a[i].id = i;
}
for(int i = 1; i <= m; i++){
int x;
cin >> b[i].l >> b[i].r >> x;
b[i].val=a[x].val;
b[i].id = i;
}
sort(a + 1, a + n + 1, cmp);
sort(b + 1,b + m + 1, cmp);
int q = 1;
for(int i = 1; i <= m; i++){
while(q <= n && a[q].val <= b[i].val){
update(a[q].id, 1, n, 1);
q++;
}
ans[b[i].id] = b[i].l-1+query(b[i].l, b[i].r, 1, n, 1);
}
for(int i=1; i <= m; i++){
cout<<ans[i]<<endl;
}
}
}题解：
由于 0≤ai(modp)+aj(modp)<2p，我们可以将 f(i,j)的值分为两类。一类是 0≤ai(modp)+aj(modp)<p0 ，另一类是 p≤ai(modp)+aj(modp)<2p
对于第一类，我们需要实现的功能是：查询区间内小于 p−ai 的最大的数；对于第二类，只需要找到 aj 的最大值即可。
第二类很好解决，主要是第一类，问题转化成如何查询区间内小于 p−ai的最大的数，没有修改。
std 的做法是建立一个线段树，每个节点用一个 vector 存放区间内的所有数。对于查询，找到这个区间对应的 log个节点，然后在节点对应的 vector 内二分查找小于 p−ai 的最大的数，然后把这些节点的结果求个最大值。
在建立线段树的时候可以使用归并排序实现，查询时需要找到区间对应的 log个节点，然后需要在每个节点的 vector 内二分。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
#define ls u << 1
#define rs u << 1 | 1
struct Tree
{
int l, r;
}t[N << 2];
int a[N],l[N], r[N];
int p;
pair<int, int> v[20][N];
void build(int u, int l, int r, int h)
{
t[u].l = l;
t[u].r = r;
if(l == r)
{
v[h][l] = {a[l], l};
return;
}
int mid = l + r >> 1;
build(ls, l, mid, h + 1);
build(rs, mid + 1, r, h + 1);
//归并排序
int i = t[ls].l, j = t[rs].l;
int cnt = t[u].l;
while(i <= t[ls].r && j <= t[rs].r)
{
if (v[h + 1][i] < v[h + 1][j]) v[h][cnt++] = v[h + 1][i++];
else v[h][cnt++] = v[h + 1][j++];
}
while(i <= t[ls].r) v[h][cnt++] = v[h + 1][i++];
while(j <= t[rs].r) v[h][cnt++] = v[h + 1][j++];
}
pair<int, int> mx, pre;
#define l t[u].l
#define r t[u].r
void query(int u, int x, int y, int h, int val)
{
if (x > r || y < l) return;
if(x <= l && r <= y)
{
mx = max(mx, v[h][r]);
int pos = upper_bound(v[h] + l, v[h] + r + 1, pair<int, int> (val, -1)) - v[h];
if (pos - 1 >= l) pre = max(pre, v[h][pos - 1]);
return;
}
query(ls, x, y, h + 1, val);
query(rs, x, y, h + 1, val);
}
#undef l
#undef r
#undef ls
#undef rs
int cal_pos(int l, int r, int x)
{
pre = mx = {-1, -1};
query(1, l, r, 0, p - x);
int ppre = pre.second;
int pmx = mx.second;
if (ppre != -1 && x + a[ppre] > (x + a[pmx]) % p) return ppre;
else return pmx;
}
struct node
{
int v, x, y, l, r;
friend bool operator <(node a,node b)
{
return a.v<b.v;
}
};
void solve()
{
int n, k, i, pos;
cin >> n >> p >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] %= p;
}
for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
build(1, 1, n, 0);
priority_queue<node>q;
for (int i = 1; i <= n; i++)
{
pos = cal_pos(l[i], r[i], a[i]);
q.push({(a[i] + a[pos]) % p, i, pos, l[i], r[i]});
}
vector<int> res;
while(q.size() && res.size() < k)
{
node t = q.top();
q.pop();
res.push_back(t.v);
if (t.y - 1 >= t.l)
{
pos = cal_pos(t.l, t.y - 1, a[t.x]);
q.push({(a[t.x] + a[pos]) % p, t.x, pos, t.l, t.y - 1});
}
if (t.y + 1 <= t.r)
{
pos = cal_pos(t.y + 1, t.r, a[t.x]);
q.push({(a[t.x] + a[pos]) % p, t.x, pos, t.y + 1, t.r});
}
}
while(res.size() < k) res.push_back(-1);
for (auto i : res) cout << i << " ";
cout << "\n";
}
signed main()
{
int t;
cin >> t;
while(t--) solve();
return 0;
}456线段树+离线询问+Trie树
1.HH的项链--区间颜色**
题解：1. 询问的是一个区间;
2. 对于同一种贝壳，如果在询问的区间中重复出现，那么就可以只关注它出现的某一个位置而忽略其他同类的贝壳。
我们要关注在区间内哪一个位置的同类贝壳。因为在一个区间中除了端点以外，其它中间元素的位置和数目都是不确定的，所以一种思路显而易见：只关注在两端点处出现的同类贝壳。
既然只关注最右边的贝壳，那么就需要依次从左向右地处理和修改整个数组，这样才能保证我们对于前一个区间的修改不会影响到后面区间的询问。在关注了最右边贝壳之后，要忽略区间内其他同类的贝壳。
我们要对区间询问对于每一个区间，询问在它右端点之前有多少不同类的贝壳
总思路：
- 我们需要一种支持单点修改、区间查询的数据结构
- 对给定的询问区间，按照区间右端点进行排序，按排序后的顺序记录答案，然后原序输出。
- 每个询问区间的答案就是区间右端点的前缀和−(区间左端点−1)的前缀和。
代码：
#include<bits/stdc++.h>
#define maxn 1000010
using namespace std;
int n,m;
int a[maxn],ans[maxn];
int vis[maxn],tree[maxn];
struct QUE{
int l;
int r;
int id;
}q[maxn];
inline void read(int &x){
char ch=getchar();int f=1;x=0;
while(!isdigit(ch) && ch^'-') ch=getchar();
if(ch=='-') f=-1,ch=getchar();
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
x*=f;
}
inline bool cmp(const QUE &a,const QUE &b){
return a.r<b.r;
}
inline int lowbit(int x){
return x&(-x);
}
void modify(int p,int v){
for(;p<=n;p+=lowbit(p))
tree[p]+=v;
}
int query(int p){
int res=0;
for(;p;p-=lowbit(p))
res+=tree[p];
return res;
}
int main(){
read(n);
for(rint i=1;i<=n;++i) read(a[i]);
read(m);
for(rint i=1;i<=m;++i){
read(q[i].l); read(q[i].r); q[i].id=i;
}
sort(q+1,q+m+1,cmp);
int pow=1;
for(rint i=1;i<=m;++i){
for(rint j=pow;j<=q[i].r;++j){
if(vis[a[j]]) modify(vis[a[j]],-1);
modify(j,1);
vis[a[j]]=j;
}
pow=q[i].r+1;
ans[q[i].id]=query(q[i].r)-query(q[i].l-1);
}
for(rint i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}2.Notpad*****
题解：暂时空上，对照别人代码写的，还会二刷
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
int n, m, ch[N][26], tot, pre[N], s[N];
int ans[100005], a[100005][17], logn[100005];
string str[100005];
int lowbit(int x) { return x & -x; }
void add(int x, int y)
{
while (x < N)
{
s[x] += y;
x += lowbit(x);
}
}
int query(int x)
{
int res = 0;
while (x)
{
res += s[x];
x -= lowbit(x);
}
return res;
}
int ask(int l, int r) {
return query(r) - query(l - 1);
}
void insert(string &s, int cur)//z字典树
{
int p = 0;
for (char c : s)
{
if (!ch[p][c - 'a'])
ch[p][c - 'a'] = ++tot;
p = ch[p][c - 'a'];
if (pre[p])
add(pre[p], -1);
add(cur, 1);
pre[p] = cur;
}
}
vector<pair<int, int>> qry[100005];
int query1(int l, int r)
{
int s = logn[r - l + 1];
assert(0 <= s and s <= 16);
return max(a[l][s], a[r - (1 << s) + 1][s]);
}
void solve() {
cin >> n >> m;
logn[0] = -1;
for (int i = 1; i <= n; i++) {
cin >> str[i];
a[i][0] = str[i].length();
logn[i] = logn[i >> 1] + 1;
}
for (int j = 1; j <= 16; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
for (int i = 1, l, r; i <= m; i++)
{
cin >> l >> r;
qry[r].push_back({l, i});
}
for (int i = 1; i <= n; i++)
{
insert(str[i], i);
for (auto &[l, id] : qry[i])
ans[id] = ask(l, i) * 2 - query1(l, i);
}
for (int i = 1; i <= m; i++)
cout << ans[i] << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
while(_--) {
solve();
}
return 0;
}
3.