//https://codeforces.com/gym/104053/problem/E
结构体封装了两棵线段树，实测比不封装块！
pre.query(1,1,p,1,len) 是目前比b[p]小的数的总和！b为a的离散化数组！
pre.query_cnt(1,1,p,1,len) 是目前比b[p]小的数字的个数！
nex.query(1,1,p,1,len) 是总共比b[p]小的数字总和！
nex.query_cnt(1,1,p,1,len) 是总共比b[p]小的数字的总和！
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<map>
#include<unordered_map>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int N = 1e6+9;
int a[N],b[N];
int n,m;
struct SegmentTree {
ll sum[N << 2];
int cnt[N <<2 ];
void pushup(int u) {
sum[u] = sum[u<<1] + sum[u<<1|1];
cnt[u] = cnt[u<<1] + cnt[u<<1|1];
}
void build(int u,int l,int r) {
sum[u] = 0,cnt[u] = 0;
if(l == r) return;
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void modify(int u,int x,int c,int l,int r) {
if(l == x && r == x) {
sum[u] += c;
cnt[u]++;
return;
}
int mid = l + r >> 1;
if(x <= mid) modify(u<<1,x,c,l,mid);
else modify(u<<1|1,x,c,mid+1,r);
pushup(u);
}
ll query(int u,int l,int r,int L,int R) {
if(l <= L && r >= R) {
return sum[u];
}
ll ans = 0;
int mid = L + R >> 1;
if(l <= mid) ans = query(u<<1,l,r,L,mid);
if(r > mid) ans += query(u<<1|1,l,r,mid+1,R);
return ans;
}
ll query_cnt(int u,int l,int r,int L,int R) {
if(l <= L && r >= R) {
return cnt[u];
}
ll ans = 0;
int mid = L + R >> 1;
if(l <= mid) ans = query_cnt(u<<1,l,r,L,mid);
if(r > mid) ans += query_cnt(u<<1|1,l,r,mid+1,R);
return ans;
}
}pre,nex;
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i=1; i<=n; i++) cin >> a[i],b[i] = a[i];
sort(b+1,b+n+1);
int len = unique(b+1,b+n+1) - b - 1;
nex.build(1,1,len);
pre.build(1,1,len);
for(int i=1; i<=n; i++) {
int p = lower_bound(b+1,b+len+1,a[i]) - b;
nex.modify(1,p,a[i],1,len);
}
for(int i=1; i<=n; i++) {
int p = lower_bound(b+1,b+len+1,a[i]) - b;
pre.modify(1,p,a[i],1,len);
ll t1 = pre.query(1,1,p,1,len);
ll t2 = nex.query(1,1,p,1,len);
ll cnt1 = pre.query_cnt(1,1,p,1,len);
ll cnt2 = nex.query_cnt(1,1,p,1,len);
ll ans1 = 1LL*a[i] * (cnt1 - 1) - (t1 - a[i]) + cnt1 - 1;
ll ans2 = 1LL*a[i] * (cnt2 - cnt1) - (t2 - t1);
ll ans = ans1 + ans2;
if(ans <= m-2) cout<<ans<<"\n";
else cout<<-1<<"\n";
}
return 0;
}
动态开点权值线段树带有区间修改
无build()函数，还不太清楚！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9+7;
const int MAXN = 1e5+9;
struct Node {
int cnt,del,lc,rc;
}tree[MAXN * 50];
int tot;
void pushup(int u) {
tree[u].cnt = tree[tree[u].lc].cnt + tree[tree[u].rc].cnt;
}
void movetag(int u) {
tree[u].del = 1;
tree[u].cnt = 0;
}
void pushdown(int u) {
if(tree[u].del) {
tree[u].del = 0;
movetag(tree[u].lc);
movetag(tree[u].rc);
}
}
void insert(int u,int l,int r,int x) {
if(l == r) {
tree[u].del = 0;
tree[u].cnt++;
return;
}
pushdown(u);
int mid = l + r >> 1;
if(x <= mid) {
if(tree[u].lc == 0) tree[u].lc = ++tot;
insert(tree[u].lc,l,mid,x);
} else {
if(tree[u].rc == 0) tree[u].rc = ++tot;
insert(tree[u].rc,mid+1,r,x);
}
pushup(u);
}
void modify(int u,int lc,int rc,int l,int r) {
if(u == 0 || tree[u].del == 1 || tree[u].cnt == 0) return;
if(l <= lc && r >= rc) {
tree[u].del = 1;
tree[u].cnt = 0;
return;
}
int mid = lc + rc >> 1;
pushdown(u);
if(l <= mid) {
modify(tree[u].lc,lc,mid,l,r);
}
if(r > mid) {
modify(tree[u].rc,mid+1,rc,l,r);
}
pushup(u);
}
int query_sum(int u,int lc,int rc,int l,int r) {
if(u == 0 || tree[u].del == 1 || tree[u].cnt == 0) return 0;
if(l <= lc && r >= rc) return tree[u].cnt;
pushdown(u);
int sum = 0;
int mid = lc + rc >> 1;
if(l <= mid) sum = query_sum(tree[u].lc,lc,mid,l,r);
if(r > mid) sum += query_sum(tree[u].rc,mid+1,rc,l,r);
return sum;
}
int query_k(int u,int lc,int rc,int l,int r,int k) {
if(u == 0 || tree[u].cnt == 0 || tree[u].del == 1) return -1;
if(lc == rc) {
if(tree[u].cnt >= k) return lc;
else return -1;
}
pushdown(u);
int cnt = 0;
int mid = lc + rc >> 1;
if(r > mid) {
cnt = query_sum(tree[u].rc,mid+1,rc,l,r);
if(cnt >= k) return query_k(tree[u].rc,mid+1,rc,l,r,k);
}
if(l <= mid) {
return query_k(tree[u].lc,lc,mid,l,r,k - cnt);
}
return - 1;
}
int main() {
tot = 1;
int n;
cin >> n;
for(int i=1; i<=n; i++) {
int op,l,r,k;
scanf("%d",&op);
if(op == 1) {
int x;
scanf("%d",&x);
insert(1,1,INF,x);
} else if(op == 2) {
scanf("%d%d",&l,&r);
modify(1,1,INF,l,r);
} else {
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",query_k(1,1,INF,l,r,k));
}
}
return 0;
}
权值线段树！
https://codeforces.com/contest/1042/problem/D
题目大意：
给定一段序列，求满足条件的部分子段序列和小于t的个数！
容易想到前缀和,题目要求等价于 sum[r] - sum[l-1] < t;
然后枚举l,r 但是这样也只能将复杂度n3降到n2，继续考虑将式子变形： sum[r] < t + sum[l-1];
离散化后建立权值线段树，求满足条件r的个数!
枚举l，log查询r，时间复杂度 nlog(n),写出超多bug吐~;
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+9;
typedef long long ll;
ll a[N],b[N];
ll sum[N];
ll n,t;
struct Segmentree
{
int l,r,v;
} tr[N<<2];
void pushup(int u)
{
tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
}
void build(int u,int l,int r)
{
tr[u] = {l,r,0};
if(l == r) return;
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
}
void modify(int u,int x)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u].v++;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u<<1,x);
else modify(u<<1|1,x);
pushup(u);
}
void change(int u,int x)
{
if(tr[u].l == x && tr[u].r == x)
{
tr[u].v--;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) change(u<<1,x);
else change(u<<1|1,x);
pushup(u);
}
ll query(int u,int l,int r)
{
if(l <= tr[u].l && r >= tr[u].r)
{
return tr[u].v;
}
ll ans = 0;
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) ans = query(u<<1,l,r);
if(r > mid) ans += query(u<<1|1,l,r);
return ans;
}
int main()
{
cin >> n >> t;
for(int i=1; i<=n; i++) scanf("%lld",&a[i]),sum[i] = sum[i-1] + a[i],b[i] = sum[i];
sort(b+1,b+n+1);
int len = unique(b+1,b+n+1) - b - 1;
build(1,1,n); //建树len不就可以了吗？
for(int i=1; i<=n; i++)
{
int temp = lower_bound(b+1,b+len+1,sum[i]) - b;
modify(1,temp);
}
ll ans = 0;
for(int l=1; l<=n; l++)
{
ll x = t + sum[l-1] - 1;
int temp = upper_bound(b+1,b+len+1,x) - b - 1;
if(temp >= 1 && temp <= n) ans += query(1,1,temp);
temp = upper_bound(b+1,b+len+1,sum[l]) - b - 1;
if(temp >= 1 && temp <= n) change(1,temp);
}
cout<<ans<<"\n";
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=1394
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+9;
int a[N];
typedef long long ll;
int n,len;
struct Segmentree {
int l,r;
int v;
}tr[N<<2];
void pushup(int u) {
tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
}
void build(int u,int l,int r) {
tr[u].l = l,tr[u].r = r,tr[u].v = 0;
if(l == r) return;
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1 | 1,mid+1,r);
}
void modify(int u,int x) {
if(tr[u].l == x && tr[u].r == x) {
tr[u].v++;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u<<1,x);
else modify(u<<1|1,x);
pushup(u);
}
ll query(int u,int l,int r) {
if(l <= tr[u].l && r >= tr[u].r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;
ll ans = 0;
if(l <= mid) ans = query(u<<1,l,r);
if(r > mid) ans += query(u<<1|1,l,r);
return ans;
}
int main() {
while(~scanf("%d",&n)) {
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
build(1,0,n-1);
ll sum = 0;
for(int i=1; i<=n; i++) {
sum += query(1,a[i]+1,n-1);
modify(1,a[i]);
}
ll minn =sum;
for(int i=1;i<=n-1;i++) {
sum += (n-a[i]-1)-a[i];
minn = min(minn,sum);
}
printf("%lld\n",minn);
}
return 0;
}
权值线段树求逆序对!
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+9;
int a[N],b[N];
typedef long long ll;
int n,len;
struct Segmentree {
int l,r;
int v;
}tr[N<<2];
void pushup(int u) {
tr[u].v = tr[u<<1].v + tr[u<<1|1].v;
}
void build(int u,int l,int r) {
tr[u].l = l,tr[u].r = r;
if(l == r) return;
int mid = l + r >> 1;
build(u<<1,l,mid),build(u<<1 | 1,mid+1,r);
}
void modify(int u,int x) {
if(tr[u].l == x && tr[u].r == x) {
tr[u].v++;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u<<1,x);
else modify(u<<1|1,x);
pushup(u);
}
ll query(int u,int l,int r) {
if(l <= tr[u].l && r >= tr[u].r) return tr[u].v;
int mid = tr[u].l + tr[u].r >> 1;
ll ans = 0;
if(l <= mid) ans = query(u<<1,l,r);
if(r > mid) ans += query(u<<1|1,l,r);
return ans;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
b[i] = a[i];
}
build(1,1,n);
sort(b+1,b+n+1);
len = unique(b+1,b+n+1) - b - 1;
ll ans = 0;
for(int i=1; i<=n; i++) {
int temp = lower_bound(b+1,b+len+1,a[i]) - b;
if(temp != n) ans += query(1,temp+1,n); //这里不特判应该也不会RE！
modify(1,temp);
}
cout<<ans<<"\n";
return 0;
}
京公网安备 11010502036488号