题意描述

给定一个数组arr,对数组a[id[i]]进行q次更新为val，每次统计数组中连续子数组（不一定连续）的最少数量seq[i]，在询问结束后结束后，输出sigma（i*seq[i]); 连续子子数组定义为：

解析

先用set计算出现有最少连续子序列的数量count；对于每次更新，相应判断count的值，即可，详见代码

#include <bits/stdc++.h>
using namespace std;
long int mod=1000000007 ; 
int main(){
    int n;cin>>n;
    multiset<int> set1;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
        set1.insert(arr[i]);
    }
    multiset<int> set2=set1;//拷贝一个集合
    int count=0;
    while(set2.size()){//统计现有数量，尽可能找出最长的连续子数组
        count++;
        int cur=*(set2.begin());
        set2.erase(set2.find(cur));
        while((set2.find(cur+1))!=set2.end()){
            cur++;
            set2.erase(set2.find(cur));//每次找到cur+1都删去该数
        }
    }
   long long int q;
    cin>>q;
    long long int ans=0;
    for(long long int i=0;i<q;i++){
        int id,val;
        cin>>id>>val;
        id--;
        
        int curr=set1.count(arr[id]);
        int prev=set1.count(arr[id]-1);
        int next=set1.count(arr[id]+1);
        
        if(curr>max(prev,next))//大于旁边两者 数量减一
            count--;
        else if(curr<=min(prev,next))//小于等于旁边两者 数量加一
            count++;
        
        set1.erase(set1.find(arr[id]));//删去该数
        arr[id]=val;
        
        curr=set1.count(arr[id]);//添加一个数，同理
        prev=set1.count(arr[id]-1);
        next=set1.count(arr[id]+1);
        
        if((curr+1)>max(prev,next))
            count++;
        else if((curr+1)<=min(prev,next))
            count--;
        
        set1.insert(val);
        ans=(ans+((i+1)*(count))%mod)%mod;
    }
    cout<<ans;
    return 0;
}