CF 1167 E.Range Deleting & F.Scalar Queries | edu round 65

（有任何问题欢迎留言或私聊 && 欢迎交流讨论哦

Catalog

Problem：传送门

 Portal
 原题目描述在最下面。

E.Range Deleting

• 题意：
  给你一段长度为$n$n值域为$[1, m]$[1,m]的序列，$n,m\le 1e6$n,m≤1e6。
  问有多少对$pair(l,r)$pair(l,r)满足，原序列删除值在$[l,r]$[l,r]范围内的数字后，序列单调不递减。
  
  
• 观察：
  如果原序列本来就单调不递减，那答案就是$m*(m+1)/2$m∗(m+1)/2。
  令$ls[x]$ls[x]表示值$x$x第一次出现的位置，$rs[x]$rs[x]表示值$x$x最后一次出现的位置。
  若序列本来不是单调不递减，就是存在$a,b$a,b满足：$1\le a\lt b\le m,rs[a]\gt ls[b]$1≤a<b≤m,rs[a]>ls[b]。
  我们找到第一次出现矛盾的值$x$x和最后一次出现矛盾的值$y$y。即$rs[x-1]\gt ls[x]$rs[x−1]>ls[x]，$rs[y]\gt ls[y+1]$rs[y]>ls[y+1]。
  观察可知：$pair(l,r)$pair(l,r)必须满足：$l\le x\;||\;r\ge y$l≤x∣∣r≥y。
  
  
• 解析：
  从上面我们得到了$pair(l,r)$pair(l,r)种$l$l的上界和$r$r的下界。
  考虑枚举$r$r，找到能满足条件的最大的$l$l，那么剩下的$1,2,...,l-1$1,2,...,l−1做左端点肯定也是满足条件的$pair$pair。这个道理应该很明显。
  显然如果你从大到小的枚举$r$r，他们满足条件的最大的$l$l肯定是单调不递增的。
  然后就随便$O(n)$O(n)计数了。就这样找$l$l，while(rs[x-1] > ls[i+1]) -- x;
  因为你只要知道删除$pair(l,r)$pair(l,r)后，能满足$rs[l-1]\lt ls[r+1]$rs[l−1]<ls[r+1]即可。
  
  
• 细节：
  因为有的数字没有出现过，所以找$x,y$x,y的时候，先离散化一下在找比较方便。
  比如：$3$3 $1$1。没有出现$2$2，这时候$x=3,y=1$x=3,y=1。因为$rs[1]\gt ls[3]$rs[1]>ls[3]。
  还有就是对于没出现过的数字他的$ls[]和rs[]$ls[]和rs[]怎么赋值呢？
  因为在算答案贡献的时候，只关心小数字的$rs[]$rs[]和大数字的$ls[]$ls[]。
  所以对不存在的数就：$rs[x]=rs[x-1[,ls[x]=ls[x+1]$rs[x]=rs[x−1[,ls[x]=ls[x+1]。
• 总结：
  只要你发现了那个观察，这个题就是一个傻逼题啊。

#include<bits/stdc++.h>
#define fi first
#define se second
#define iis std::ios::sync_with_stdio(false)
#define eb emplace_back
#define o2(x) (x)*(x)
#define all(x) (x).begin(), (x).end()
#define BASE_MAX 62
#define debug(x) cout << "[" << x << "]\n"
#define endl "\n"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
inline LL read(){
  LL x=0;int f=0;char ch=getchar();
  while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
  while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return x=f?-x:x;
}
inline void write(LL x) {
    if(x==0){putchar('0'),putchar('\n');return;}
    if(x < 0) {putchar('-');x=-x;}
    static char s[23];int l = 0;
    while(x!=0)s[l++]=x%10+48,x/=10;
    while(l)putchar(s[--l]);
    putchar('\n');
}
template<class T>T Max(T a1,T a2){ return a1>a2?a1:a2; }
template<class T>T Max(T a1,T a2,T a3){ return Max(a1,Max(a2,a3)); }
template<class T>T Max(T a1,T a2,T a3,T a4){ return Max(a1,a2,Max(a3,a4)); }
template<class T>T Min(T a1,T a2){ return a1<a2?a1:a2; }
template<class T>T Min(T a1,T a2,T a3){ return Min(a1,Min(a2,a3)); }
template<class T>T Min(T a1,T a2,T a3,T a4){ return Min(a1,a2,Min(a3,a4)); }
const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int HMOD[] = {1000000007, 1000000009};
const LL BASE[] = {1572872831, 1971536491};
const int MXN = 1e6 + 7;

int n, m;
int ar[MXN];
int ls[MXN], rs[MXN];
int main() {
    n = read(), m = read();
    std::vector<int> vs; vs.eb(0);
    for(int i = 1; i <= n; ++i) ar[i] = read(), rs[ar[i]] = i, vs.eb(ar[i]);
    for(int i = n; i >= 1; --i) ls[ar[i]] = i;
    ls[m+1] = n+1;
    for(int i = 2; i <= m; ++i) if(rs[i] == 0) rs[i] = rs[i-1];
    for(int i = m; i >= 1; --i) if(ls[i] == 0) ls[i] = ls[i+1];
    //for(int i = 0; i <= m + 1; ++i) printf("%d %d*\n", ls[i], rs[i]);
    int x = -1, y = -1;
    sort(all(vs)); vs.erase(unique(all(vs)), vs.end());
    for(int i = 1; i < vs.size(); ++i) if(ls[vs[i]] < rs[vs[i-1]]){
        x = vs[i]; break;
    }
    for(int i = vs.size()-2; i >= 0; --i) if(rs[vs[i]] > ls[vs[i+1]]){
        y = vs[i]; break;
    }
    //printf("%d %d\n", x, y);
    if(x == -1) {
        write((LL)m*(m+1)/2);
        return 0;
    }
    LL ans = 0;
    for(int i = m; i >= y; --i) {
        while(rs[x-1] > ls[i+1]) -- x;
        ans += x;
        //debug(x);
    }
    write(ans);
    return 0;
}

F.Scalar Queries

• 题意：
  求$\sum_{1\le l\le r\le n}f(l,r)$∑1≤l≤r≤n​f(l,r)。$f(l,r)=\sum_{i=1}^{r-l+1} i*ar[i]$f(l,r)=∑i=1r−l+1​i∗ar[i]，数组$ar$ar是把原数组的$[l,r]$[l,r]部分从小到大排序后得到的新数组。
• 人尽皆知：
  首先$\sum_{1\le l\le r\le n}g(l,r)$∑1≤l≤r≤n​g(l,r)，$g(l,r)=\sum_{i=l}^r a[i]$g(l,r)=∑i=lr​a[i]。这个式子应该是随便算的吧？
  对每个数字算贡献，数字$x$x包含它的区间有$cnt=i\times (n-i+1)$cnt=i×(n−i+1)个，贡献就是：$x\times cnt$x×cnt。
• 解析：
  还是算单个数字的贡献。
  考虑如果有一个数字$y$y，它比$x$x小。那么只要$x,y$x,y在一个区间内，这个$y$y的存在肯定会让值$x$x的贡献增加一次。
  那么这个$y$y使得$x$x增加的总贡献是多少次呢？
  答案是：若$y$y在$x$x前面：$place[y]\times (n-place[x]+1)$place[y]×(n−place[x]+1)；若$y$y在$x$x后面：$place[x]\times (n-place[y]+1)$place[x]×(n−place[y]+1)。
  既然这样，我就从前往后和从后往前算两次算贡献即可。
  很明显这个东西用一个树状数组维护就可以了。相当于权值线段树吧？就是每个点代表的是权值，维护的是他的下标值，就是他的位置。
  看代码就懂了。

#include<bits/stdc++.h>
#define fi first
#define se second
#define iis std::ios::sync_with_stdio(false)
#define eb emplace_back
#define o2(x) (x)*(x)
#define all(x) (x).begin(), (x).end()
#define BASE_MAX 62
#define debug(x) cout << "[" << x << "]\n"
#define endl "\n"
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
inline LL read(){
  LL x=0;int f=0;char ch=getchar();
  while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
  while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return x=f?-x:x;
}
inline void write(LL x) {
    if(x==0){putchar('0'),putchar('\n');return;}
    if(x < 0) {putchar('-');x=-x;}
    static char s[23];int l = 0;
    while(x!=0)s[l++]=x%10+48,x/=10;
    while(l)putchar(s[--l]);
    putchar('\n');
}
int lowbit(int x) {return x&(-x);}
template<class T>T Max(T a1,T a2){ return a1>a2?a1:a2; }
template<class T>T Max(T a1,T a2,T a3){ return Max(a1,Max(a2,a3)); }
template<class T>T Max(T a1,T a2,T a3,T a4){ return Max(a1,a2,Max(a3,a4)); }
template<class T>T Min(T a1,T a2){ return a1<a2?a1:a2; }
template<class T>T Min(T a1,T a2,T a3){ return Min(a1,Min(a2,a3)); }
template<class T>T Min(T a1,T a2,T a3,T a4){ return Min(a1,a2,Min(a3,a4)); }

const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int HMOD[] = {1000000009, 1004535809};
const LL BASE[] = {1572872831, 1971536491};
const int mod = 1e9 + 7;
const int MXN = 1e6 + 7;

LL bit[MXN];
void bit_add(int x, int v, int N) {while(x <= N+1) bit[x] += v, x += lowbit(x);}
LL bit_sum(int x) {LL ans=0;for(;x;x-=lowbit(x))ans+=bit[x];return ans%mod;}
int n, m;
LL ar[MXN], ans;
int br[MXN];
std::vector<int> vs;
int get_id(int x) {return lower_bound(all(vs), x)-vs.begin()+1;}
int main() {
#ifndef ONLINE_JUDGE
    freopen("E://ADpan//in.in", "r", stdin);
    //freopen("E://ADpan//out.out", "w", stdout);
#endif
    n = read();
    for(int i = 1; i <= n; ++i) ar[i] = read(),vs.eb(ar[i]),ans=(ans+ar[i]*i%mod*(n-i+1)%mod)%mod;
    sort(all(vs));
    assert((int)vs.size() == n);
    for(int i = 1; i <= n; ++i) {
        br[i] = get_id(ar[i]);
        ans = (ans + bit_sum(br[i]-1)*(n-i+1)%mod*ar[i]%mod)%mod;
        bit_add(br[i], i, n);
    }
    for(int i = 0; i <= n+1; ++i) bit[i] = 0;
    for(int i = n; i >= 1; --i) {
        ans = (ans + bit_sum(br[i]-1)*i%mod*ar[i]%mod)%mod;
        bit_add(br[i], n-i+1, n);
    }
    write((ans%mod+mod)%mod);
    return 0;
}

Problem Description：