1🐋🐋配对最小值（王者；树状数组）

时间限制：1秒

占用内存：64M

🐟题目思路

MT3065 配对最小值_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
using namespace std;
const int N=1e5+7;
int a[N],b[N],c[N],n,q;
struct QUERY{int l,r,id;
}query[N];
vector<pair<int,int> > items;
int lowbit(int x){return x&(-x);}
void update(int i,int x){for(;i<=n;i+=lowbit(i)) c[i]+=x;
}
int sum(int i){int ans=0;for(;i>0;i-=lowbit(i)) ans+=c[i];return ans;
}
bool cmp1(int x,int y){return a[x]<a[y];}
bool cmp2(pair<int,int> a,pair<int,int> b){return a.first>b.first;}
bool cmp3(QUERY a,QUERY b){return a.l>b.l;}
int main( )
{cin>>n>>q;for(int i=1;i<=n;i++){cin>>a[i];b[i]=i;}sort(b+1,b+1+n,cmp1);items.push_back({b[1],b[2]});items.push_back({b[n-1],b[n]});for(int i=2;i<n;i++){int val1=a[b[i]]-a[b[i-1]];int val2=a[b[i+1]]-a[b[i]];if(val1<=val2) items.push_back({b[i],b[i-1]});if(val2<=val1) items.push_back({b[i],b[i+1]});}for(auto &it:items)if(it.first>it.second)swap(it.first,it.second);sort(items.begin(),items.end(),cmp2);//降序for(int i=1;i<=q;i++) cin>>query[i].l>>query[i].r,query[i].id=i;sort(query+1,query+1+q,cmp3);int pos=0;long long ans=0;for(int i=1;i<=q;i++){while(pos<items.size()&&query[i].l<=items[pos].first)update(items[pos++].second,1);ans+=query[i].id*sum(query[i].r);}cout<<ans;return 0;
}

2🐋🐋三元组逆序对（星耀；树状数组）

时间限制：1秒

占用内存：64M

🐟题目思路

MT3067 三元组逆序对_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
using namespace std;
#define int long long
const int N=5e5+7;
int n,a[N],tmp[N],c[N],ans,pre[N],suf[N];
int lowbit(int x){return x&(-x);}
void update(int i,int x){for(;i<=n;i+=lowbit(i)) c[i]+=x;
}
int sum(int i){int ans=0;for(;i>0;i-=lowbit(i)) ans+=c[i];return ans;
}
int sum(int l,int r){return sum(r)-sum(l-1);}signed main( )
{cin>>n;for(int i=1;i<=n;i++) cin>>a[i];//离散化for(int i=1;i<=n;i++) tmp[i]=a[i];sort(tmp+1,tmp+1+n);int len=unique(tmp+1,tmp+1+n)-(tmp+1);for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,tmp+1+len,a[i])-tmp;//顺着看，前面多少数比自己大for(int i=1;i<=n;i++){update(a[i],1);pre[i]=sum(a[i]+1,n);}memset(c,0,sizeof(c));//逆着看，前面多少数比自己小for(int i=n;i>=1;i--){update(a[i],1);suf[i]=sum(a[i]-1);}for(int i=1;i<=n;i++) ans+=pre[i]*suf[i];cout<<ans;return 0;
}

3🐋🐋粉刷匠（星耀；线段树）

时间限制：1秒

占用内存：64M

🐟题目思路

MT3068 粉刷匠_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
using namespace std;
const int N=5e4+10;
int a[N][15];
//num1初始化后的固定属性，相应区域1的个数；lz懒标记；ans是正确的个数，动态变化
struct NODE{int l,r,num1,lz,ans;
}tree[16][4*N];
void build(int tr,int p,int l,int r){tree[tr][p].lz=-1;tree[tr][p].l=l,tree[tr][p].r=r;if(l==r){tree[tr][p].num1=a[l][tr];tree[tr][p].ans=(a[l][tr]==0?1:0);return;}int mid=l+((r-l)>>1);build(tr,p*2,l,mid);build(tr,p*2+1,mid+1,r);tree[tr][p].num1=tree[tr][p*2].num1+tree[tr][p*2+1].num1;tree[tr][p].ans=tree[tr][p*2].ans+tree[tr][p*2+1].ans;
}
void lazy(int tr,int p,int v){int s=tree[tr][p].l,t=tree[tr][p].r;tree[tr][p].lz=v;if(v) tree[tr][p].ans=tree[tr][p].num1;else tree[tr][p].ans=t-s+1-tree[tr][p].num1;
}
void pushdown(int tr,int p){lazy(tr,2*p,tree[tr][p].lz);lazy(tr,2*p+1,tree[tr][p].lz);tree[tr][p].lz=-1;
}
void update(int tr,int p,int l,int r,int c){int s=tree[tr][p].l,t=tree[tr][p].r;if(l<=s&&t<=r) return lazy(tr,p,c);if(tree[tr][p].lz!=-1) pushdown(tr,p);int mid=s+((t-s)>>1);if(l<=mid) update(tr,p*2,l,r,c);if(r>mid) update(tr,p*2+1,l,r,c);tree[tr][p].ans=tree[tr][p*2].ans+tree[tr][p*2+1].ans;
}
int main( )
{int n,m,q;string str;cin>>n>>m>>q;for(int i=1;i<=n;i++){cin>>str;for(int j=1;j<=m;j++) a[i][j]=str[j-1]-'0';}for(int i=1;i<=m;i++) build(i,1,1,n);while(q--){int x1,x2,y1,y2,w,ans=0;cin>>x1>>x2>>y1>>y2>>w;for(int i=y1;i<=y2;i++) update(i,1,x1,x2,w);for(int i=1;i<=m;i++) ans+=tree[i][1].ans;cout<<ans<<endl;}return 0;
}

4🐋🐋偶数个数的异或和（星耀；树状数组）

时间限制：2秒

占用内存：125M

🐟题目思路

MT3066 偶数个数的异或和_哔哩哔哩_bilibili

🐟代码

#include<bits/stdc++.h> 
using namespace std;
const int N=1e6+7;
int n,a[N],c[N],sum[N],m,ans[N];
map<int,int> mp;
int lowbit(int x){return x&-x;}
void update(int i,int x){for(;i<=n;i+=lowbit(i)) c[i]^=x;
}
int query(int i){int ans=0;for(;i>0;i-=lowbit(i)) ans^=c[i];return ans;
}
struct QUERY{int l,r,id;bool operator<(const QUERY &x) const{return r<x.r;}
}q[N];
int main( )
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]^a[i];}cin>>m;for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].id=i;}sort(q+1,q+1+m);int pos=1;for(int i=1;i<=m;i++){while(pos<=q[i].r){if(mp.find(a[pos])!=mp.end()){update(mp[a[pos]],a[pos]);update(pos,a[pos]);mp[a[pos]]=pos;}else{mp[a[pos]]=pos;update(pos,a[pos]);}pos++;}ans[q[i].id]=sum[q[i].l-1]^sum[q[i].r]^query(q[i].r)^query(q[i].l-1);}for(int i=1;i<=m;i++) cout<<ans[i]<<endl;return 0;
}

5🐋🐋宝石的魔力波动（星耀；线段树）

时间限制：3秒

占用内存：512M

🐟题目思路

MT3069 宝石的魔力波动_哔哩哔哩_bilibili

🐟代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct NODE
{int l, r, cnt, lz;vector<int> val;
} tree[4 * N];
int n, m, a[N];
vector<int> ans;
void lazy(int p, int v)
{tree[p].lz += v;for (int i = 0; i < tree[p].cnt; i++){tree[p].val[i] += v;}
}
void pushdown(int p)
{lazy(p * 2, tree[p].lz);lazy(p * 2 + 1, tree[p].lz);tree[p].lz = 0;
}
void pushup(int p)
{vector<int> tmp;int i = 0, j = 0;int cnt_l = tree[p * 2].cnt, cnt_r = tree[p * 2 + 1].cnt;vector<int> val_l = tree[p * 2].val, val_r = tree[p * 2 + 1].val;while (i < cnt_l && j < cnt_r){tmp.emplace_back(val_l[i] > val_r[j] ? val_l[i++] : val_r[j++]);}while (i < cnt_l)tmp.emplace_back(val_l[i++]);while (j < cnt_r)tmp.emplace_back(val_r[j++]);tree[p].val.clear();for (int i = 0; i < tree[p].cnt; i++){tree[p].val.emplace_back(tmp[i]);}
}
void build(int p, int l, int r)
{tree[p].l = l, tree[p].r = r;if (l == r){tree[p].cnt = 1;tree[p].val.emplace_back(a[l]);return;}int mid = l + ((r - l) >> 1);build(p * 2, l, mid);build(p * 2 + 1, mid + 1, r);tree[p].cnt = min(tree[p * 2].cnt + tree[p * 2 + 1].cnt, 36);pushup(p);
}
void update(int l, int r, int c, int p)
{int s = tree[p].l, t = tree[p].r;if (l <= s && t <= r){return lazy(p, c);}if (tree[p].lz)pushdown(p);int mid = s + ((t - s) >> 1);if (l <= mid)update(l, r, c, p * 2);if (r > mid)update(l, r, c, p * 2 + 1);pushup(p);
}
void merge(int p)
{vector<int> tmp;int i = 0, j = 0, cnt = tree[p].cnt;vector<int> val = tree[p].val;while (i < cnt && j < ans.size()){tmp.emplace_back(val[i] > ans[j] ? val[i++] : ans[j++]);}while (i < cnt)tmp.emplace_back(val[i++]);while (j < ans.size())tmp.emplace_back(ans[j++]);ans.clear();for (int i = 0; i < min((int)tmp.size(), 36); i++)ans.emplace_back(tmp[i]);
}
void query(int l, int r, int p)
{int s = tree[p].l, t = tree[p].r;if (l <= s && t <= r){merge(p);return;}if (tree[p].lz)pushdown(p);int mid = s + ((t - s) >> 1);if (l <= mid)query(l, r, p * 2);if (r > mid)query(l, r, p * 2 + 1);return;
}
int op, l, r, v;
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> a[i];build(1, 1, n);while (m--){cin >> op >> l >> r;if (op == 1){cin >> v;update(l, r, v, 1);}else{if (l == r){cout << "-1" << endl;continue;}ans.clear();query(l, r, 1);int res = 0;for (int i = 0; i < ans.size(); i++)for (int j = i + 1; j < ans.size(); j++)res = max(res, ans[i] & ans[j]);cout << res << endl;}}return 0;
}

⭐创作不易，点个赞吧~

⭐点赞收藏不迷路~