很久以前就看到过这个题目，当时刚学线段树看了题解还是感觉敲不出来。

现在重新做这道题目感觉思路很难想到，代码量也不小，加深了对lrj大白书中pushdown和maintain的理解。

预处理从1开始到i的值。

然后一个一个更改，求和。

具体细节，包括如何找到更改的左端点和右端点，这些需要仔细思考。

thinking～～

什么时候pushdown？当你需要查找或者更改该节点以下节点信息的时候。

什么时候maintain？当某节点信息可能被你更改了。

1 #include
      
         2 #include
       
          3 #include
        
           4 #define MAXN 200001  5 #define LL long long  6 using namespace std;  7 LL sumv[800050],setv[800050],maxv[800050];  8 LL a[200005],b[200005],vis[200005],next[200005];  9 void build(LL o,LL l,LL r) 10 { 11   if (l==r) { 12     sumv[o]=b[l]; 13     maxv[o]=b[l]; 14   } 15   else{ 16     LL mid=l+(r-l)/2; 17     build(o*2,l,mid); 18     build(o*2+1,mid+1,r); 19     sumv[o]=sumv[o*2]+sumv[o*2+1]; 20     maxv[o]=max(maxv[o*2],maxv[o*2+1]); 21   } 22 } 23 void pushdown(LL o) 24 { 25   if (setv[o]>=0) 26   { 27     setv[o*2]=setv[o*2+1]=setv[o]; 28     setv[o]=-1; 29   } 30 } 31 void maintain(LL o,LL l,LL r) 32 { 33   if (setv[o]>=0){ 34     sumv[o]=setv[o]*(r-l+1); 35     maxv[o]=setv[o]; 36   } 37   else if (r>l) 38   { 39     sumv[o]=sumv[o*2]+sumv[o*2+1]; 40     maxv[o]=max(maxv[o*2],maxv[o*2+1]); 41   } 42 } 43 void update(LL o,LL l,LL r,LL y1,LL y2,LL v) 44 { 45   LL mid=l+(r-l)/2; 46   if (y1<=l&&y2>=r) setv[o]=v; 47   else{ 48     pushdown(o); 49     if (y1<=mid) update(o*2,l,mid,y1,y2,v); 50     else maintain(o*2,l,mid); 51     if (y2>mid) update(o*2+1,mid+1,r,y1,y2,v); 52     else maintain(o*2+1,mid+1,r); 53   } 54   maintain(o,l,r); 55 } 56 LL querysum(LL o,LL l,LL r,LL y1,LL y2) 57 { 58   LL mid=l+(r-l)/2,tmp=0; 59   if (setv[o]>=0) return setv[o]*(min(r,y2)-max(l,y1)+1); 60   else if (y1<=l&&y2>=r) return sumv[o]; 61   else{ 62     if (y1<=mid) tmp+=querysum(o*2,l,mid,y1,y2); 63     if (y2>mid) tmp+=querysum(o*2+1,mid+1,r,y1,y2); 64     return tmp; 65   } 66 } 67 LL querypos(LL o,LL l,LL r,LL v) 68 { 69   LL mid=l+(r-l)/2; 70   if (maxv[o]
         
          v) return querypos(o*2,l,mid,v); 75   else return querypos(o*2+1,mid+1,r,v); 76 } 77 int main() 78 { 79   LL n,p,i,tmp1,tmp2,ans; 80   while (~scanf("%I64d",&n)&&n!=0) 81   { 82     memset(vis,0,sizeof(vis));  83     p=0; 84     for (i=1;i<=n;i++) 85     { 86       scanf("%I64d",&a[i]); 87       if (a[i]>MAXN) a[i]=MAXN;  88       vis[a[i]]=1; 89       while (vis[p]) p++; 90       b[i]=p; 91     } 92     memset(vis,0,sizeof(vis)); 93     memset(next,-1,sizeof(next)); 94     for (i=1;i<=n;i++) 95     { 96       if (vis[a[i]]) next[vis[a[i]]]=i; 97       vis[a[i]]=i; 98     } 99     memset(setv,-1,sizeof(setv));100     memset(sumv,0,sizeof(sumv));101     build(1,1,n);102     ans=querysum(1,1,n,1,n);103     for (i=1;i
         
        
       
      

题目链接：