# Bzoj3747 [poi2015]kinoman

## 用线段树解决区间问题

Posted by yjjr's blog on April 10, 2018

# 题目

## Sample Input

9 4
2 3 1 1 4 1 2 4 1
5 3 6 6

15

# 分析

pre[i]表示与当前位置上的数字相同的前一个数的下标

$pre[pre[i]] + 1->pre[i]$这段位置的权值$-val[i]$，然后查询$[1, i]$的最大值即可

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define mid ((l+r)>>1)
#define lson (x<<1)
#define rson (x<<1|1)
const int maxn=1e6+6;
int n,m,a[maxn],b[maxn],pre[maxn],last[maxn];ll ans=0;
struct Seg_Tree{ll val,flag;}tree[maxn<<2];
void pushup(int x){tree[x].val=max(tree[lson].val,tree[rson].val);}
void pushdown(int x){
if(tree[x].flag){
tree[lson].val+=tree[x].flag;tree[lson].flag+=tree[x].flag;
tree[rson].val+=tree[x].flag;tree[rson].flag+=tree[x].flag;
tree[x].flag=0;
}
}
void modify(int x,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
tree[x].val+=val;
tree[x].flag+=val;
return;
}
pushdown(x);
if(ql<=mid)modify(lson,l,mid,ql,qr,val);
if(qr>mid)modify(rson,mid+1,r,ql,qr,val);
pushup(x);
}

inline ll query(int x,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return tree[x].val;
pushdown(x);
ll re=0;
if(ql<=mid)re=max(re,query(lson,l,mid,ql,qr));
if(qr>mid)re=max(re,query(rson,mid+1,r,ql,qr));
return re;
}
int main()
{