刷刷POI，整个人都POI！

BZOJ 1098: [POI2007]办公楼biu

补图联通块直接DFS出来就行了，很容易TLE要用链表及时删点、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=100010;
const int Maxm=2000010;
inline int read(){
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
struct Edge{
    int v,nxt;
    Edge(){}
    Edge(int v0,int n0){
        v=v0;
        nxt=n0;
    }
};
int head[Maxn];
Edge e[Maxm*2];
int nume;
int n,m;
inline void addEdge(int u,int v){
    e[++nume]=Edge(v,head[u]);head[u]=nume;
    e[++nume]=Edge(u,head[v]);head[v]=nume;
}
int nxt[Maxn],pre[Maxn];
inline void del(int x){
    int tmp=pre[x];
    nxt[tmp]=nxt[x];
    pre[nxt[x]]=tmp;
}
bool vis[Maxn];
int cnt;
int siz[Maxn];
bool noEdge[Maxn];
int que[Maxn];
int l,r;
int i;
void bfs(int src){
    que[0]=src;
    vis[src]=true;
    for (l = r = 0; l <= r; ++l){
        int x=que[l];
        //printf("%d\n",x);
        siz[cnt]++;
        for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=true;
        for (i=nxt[0];i<=n;i=nxt[i]){
            if (!vis[i] && !noEdge[i]){
                del(i);
                vis[i]=true;
                que[++r]=i;
            }
        }
        for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=false;
    }
}
inline void input(){
    freopen("1098.in","r",stdin);
    //freopen("1098.out","w",stdout);
}
int main(){
    //input();
    n=read();m=read();
    int x,y;
    for (i=1;i<=m;i++){
        x=read(),y=read();
        addEdge(x,y);
    }
    for (i=0;i<=n;i++){
        nxt[i]=i+1;
        pre[i+1]=i;
    }
    for (i=nxt[0];i<=n;i=nxt[i]){
        if (!vis[i]){
            cnt++;
            del(i);
            bfs(i);
        }
    }
    sort(siz+1,siz+cnt+1);
    printf("%d\n",cnt);
    for (i=1;i<=cnt;i++){
        printf("%d ",siz[i]);
    }
    printf("\n");
    return 0;
}

100

101

102

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=100010;

const int Maxm=2000010;

inline int read(){

int x = 0;

char ch = getchar();

while (ch < '0' || ch > '9')

ch = getchar();

while (ch >= '0' && ch <= '9'){

x = x * 10 + ch - '0';

ch = getchar();

}

return x;

}

struct Edge{

int v,nxt;

Edge(){}

Edge(int v0,int n0){

v=v0;

nxt=n0;

}

};

int head[Maxn];

Edge e[Maxm*2];

int nume;

int n,m;

inline void addEdge(int u,int v){

e[++nume]=Edge(v,head[u]);head[u]=nume;

e[++nume]=Edge(u,head[v]);head[v]=nume;

}

int nxt[Maxn],pre[Maxn];

inline void del(int x){

int tmp=pre[x];

nxt[tmp]=nxt[x];

pre[nxt[x]]=tmp;

}

bool vis[Maxn];

int cnt;

int siz[Maxn];

bool noEdge[Maxn];

int que[Maxn];

int l,r;

int i;

void bfs(int src){

que[0]=src;

vis[src]=true;

for (l = r = 0; l <= r; ++l){

int x=que[l];

//printf("%d\n",x);

siz[cnt]++;

for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=true;

for (i=nxt[0];i<=n;i=nxt[i]){

if (!vis[i] && !noEdge[i]){

del(i);

vis[i]=true;

que[++r]=i;

}

for (i=head[x];i;i=e[i].nxt) noEdge[e[i].v]=false;

}

inline void input(){

freopen("1098.in","r",stdin);

//freopen("1098.out","w",stdout);

}

int main(){

//input();

n=read();m=read();

int x,y;

for (i=1;i<=m;i++){

x=read(),y=read();

addEdge(x,y);

}

for (i=0;i<=n;i++){

nxt[i]=i+1;

pre[i+1]=i;

}

for (i=nxt[0];i<=n;i=nxt[i]){

if (!vis[i]){

cnt++;

del(i);

bfs(i);

}

sort(siz+1,siz+cnt+1);

printf("%d\n",cnt);

for (i=1;i<=cnt;i++){

printf("%d ",siz[i]);

}

printf("\n");

return 0;

}

BZOJ 1097: [POI2007]旅游景点atr

首先SPFA出前k+1个点的最短路,然后做状压DP.
prev[x]表示必须在x后面到达的点.DP比较随意、、
这题感觉好容易TLE！我优化了SPFA才卡时限（写的太搓怪数据？

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=20010;
const int Maxm=200010;
inline int read(){
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
int pow2[25];
struct Edge{
    int v,nxt;
    int w;
    Edge(){}
    Edge(int v0,int w0,int n0){
        v=v0;
        nxt=n0;
        w=w0;
    }
};
int head[Maxn];
Edge e[Maxm*2];
int nume;
int n,m,k;
inline void addEdge(int u,int v,int w){
    e[++nume]=Edge(v,w,head[u]);head[u]=nume;
    e[++nume]=Edge(u,w,head[v]);head[v]=nume;
}
int dist[Maxn];
bool inque[Maxn];
deque<int> que;
inline void spfa(int src){
    memset(dist,127,sizeof(dist));
    while(!que.empty()) que.pop_front();
    dist[src]=0;
    inque[src]=true;
    que.push_back(src);
    while(!que.empty()){
        int now=que.front();
        que.pop_front();
        //printf("%d\n",now);
        for (int i=head[now];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if (dist[v]>dist[now]+w){
                dist[v]=dist[now]+w;
                if (!inque[v]){
                    inque[v]=true;
                    if(!que.empty()){
                        if(dist[v]>dist[que.front()])
                            que.push_back(v);
                        else
                            que.push_front(v);
                    }else{
                        que.push_back(v);
                    }
                }
            }
        }
        inque[now]=false;
    }
}
int Ans[25][(1<<21)];
int mDist[25][Maxn];
int prev[25];
int dp(int u,int s){
    if (Ans[u][s]) return Ans[u][s];
    if (!s) return 0;
    Ans[u][s]=2100000000;
    for (int i=1;i<=k+1;i++){
        if (s&pow2[i-1] && !(prev[i]&s)){
            Ans[u][s]=min(Ans[u][s],mDist[i][u]+dp(i,s^pow2[i-1]));
        }
    }
    return Ans[u][s];
}
int getAns(int u,int s){
    int ret=2100000000;
    for (int i=1;i<=k+1;i++){
        if (s&pow2[i-1] && !(prev[i]&s)){
            ret=min(ret,mDist[i][u]+dp(i,s^pow2[i-1]));
        }
    }
    return ret;
}
int main(){
    //freopen("atr.in","r",stdin);
    //freopen("atr.out","w",stdout);
    n=read();m=read();k=read();
    for (int i=1,x,y,w;i<=m;i++){
        x=read();y=read();w=read();
        addEdge(x,y,w);
    }
    for (int i=1;i<=k+1;i++){
        spfa(i);
        for (int j=1;j<=n;j++){
            mDist[i][j]=dist[j];
        }
    }
    pow2[0]=1;
    for (int i=1;i<25;i++)pow2[i]=2*pow2[i-1];
    int p=read();
    for (int i=1,x,y;i<=p;i++){
        x=read();y=read();
        prev[x]+=pow2[y-1];
    }
    for (int i=2;i<=k+1;i++) prev[1]+=pow2[i-1];
    printf("%d\n",getAns(n,pow2[k+1]-1));
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=20010;

const int Maxm=200010;

inline int read(){

int x = 0;

char ch = getchar();

while (ch < '0' || ch > '9')

ch = getchar();

while (ch >= '0' && ch <= '9'){

x = x * 10 + ch - '0';

ch = getchar();

}

return x;

}

int pow2[25];

struct Edge{

int v,nxt;

int w;

Edge(){}

Edge(int v0,int w0,int n0){

v=v0;

nxt=n0;

w=w0;

}

};

int head[Maxn];

Edge e[Maxm*2];

int nume;

int n,m,k;

inline void addEdge(int u,int v,int w){

e[++nume]=Edge(v,w,head[u]);head[u]=nume;

e[++nume]=Edge(u,w,head[v]);head[v]=nume;

}

int dist[Maxn];

bool inque[Maxn];

deque<int> que;

inline void spfa(int src){

memset(dist,127,sizeof(dist));

while(!que.empty()) que.pop_front();

dist[src]=0;

inque[src]=true;

que.push_back(src);

while(!que.empty()){

int now=que.front();

que.pop_front();

//printf("%d\n",now);

for (int i=head[now];i;i=e[i].nxt){

int v=e[i].v,w=e[i].w;

if (dist[v]>dist[now]+w){

dist[v]=dist[now]+w;

if (!inque[v]){

inque[v]=true;

if(!que.empty()){

if(dist[v]>dist[que.front()])

que.push_back(v);

else

que.push_front(v);

}else{

que.push_back(v);

}

inque[now]=false;

}

int Ans[25][(1<<21)];

int mDist[25][Maxn];

int prev[25];

int dp(int u,int s){

if (Ans[u][s]) return Ans[u][s];

if (!s) return 0;

Ans[u][s]=2100000000;

for (int i=1;i<=k+1;i++){

if (s&pow2[i-1] && !(prev[i]&s)){

Ans[u][s]=min(Ans[u][s],mDist[i][u]+dp(i,s^pow2[i-1]));

}

return Ans[u][s];

}

int getAns(int u,int s){

int ret=2100000000;

for (int i=1;i<=k+1;i++){

if (s&pow2[i-1] && !(prev[i]&s)){

ret=min(ret,mDist[i][u]+dp(i,s^pow2[i-1]));

}

return ret;

}

int main(){

//freopen("atr.in","r",stdin);

//freopen("atr.out","w",stdout);

n=read();m=read();k=read();

for (int i=1,x,y,w;i<=m;i++){

x=read();y=read();w=read();

addEdge(x,y,w);

}

for (int i=1;i<=k+1;i++){

spfa(i);

for (int j=1;j<=n;j++){

mDist[i][j]=dist[j];

}

pow2[0]=1;

for (int i=1;i<25;i++)pow2[i]=2*pow2[i-1];

int p=read();

for (int i=1,x,y;i<=p;i++){

x=read();y=read();

prev[x]+=pow2[y-1];

}

for (int i=2;i<=k+1;i++) prev[1]+=pow2[i-1];

printf("%d\n",getAns(n,pow2[k+1]-1));

return 0;

}

因为容易TLE嘛、、我还是丢出数据好了，本机跑13S，OJ上刚好。。。。http://pan.baidu.com/s/1kTrHhND

BZOJ 1102: [POI2007]山峰和山谷Grz

直接FloodFill就好了、、网上听说会爆栈要BFS、那就写BFS好了、、

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int Maxn=1010;
int map[Maxn][Maxn];
bool vis[Maxn][Maxn];
struct Point{
    int x,y;
    Point(int x0,int y0){
        x=x0;
        y=y0;
    }
};
int flagUp,flagDown;
int low,hig;
queue<Point> que;
int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1};
int n;
inline void bfs(int x,int y){
    flagUp=flagDown=1;
    while(!que.empty()) que.pop();
    que.push(Point(x,y));
    vis[x][y]=true;
    while(!que.empty()){
        int x=que.front().x,y=que.front().y;
        que.pop();
        for (int k=0;k<8;k++){
            int tx=x+dx[k],ty=y+dy[k];
            if (1<=tx && tx<=n && 1<=ty && ty<=n){
                if (map[x][y]==map[tx][ty]){
                    if (!vis[tx][ty]){
                        que.push(Point(tx,ty));
                        vis[tx][ty]=true;
                    }
                }else{
                    if (map[tx][ty]>map[x][y])
                        flagUp=0;
                    else
                        flagDown=0;
                }
            }
        }
    }
    low+=flagDown;
    hig+=flagUp;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            scanf("%d",&map[i][j]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            if (!vis[i][j])
                bfs(i,j);
    printf("%d %d\n",hig,low);
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<queue>

#include<cstring>

using namespace std;

const int Maxn=1010;

int map[Maxn][Maxn];

bool vis[Maxn][Maxn];

struct Point{

int x,y;

Point(int x0,int y0){

x=x0;

y=y0;

}

};

int flagUp,flagDown;

int low,hig;

queue<Point> que;

int dx[]={-1,-1,0,1,1,1,0,-1};

int dy[]={0,1,1,1,0,-1,-1,-1};

int n;

inline void bfs(int x,int y){

flagUp=flagDown=1;

while(!que.empty()) que.pop();

que.push(Point(x,y));

vis[x][y]=true;

while(!que.empty()){

int x=que.front().x,y=que.front().y;

que.pop();

for (int k=0;k<8;k++){

int tx=x+dx[k],ty=y+dy[k];

if (1<=tx && tx<=n && 1<=ty && ty<=n){

if (map[x][y]==map[tx][ty]){

if (!vis[tx][ty]){

que.push(Point(tx,ty));

vis[tx][ty]=true;

}

}else{

if (map[tx][ty]>map[x][y])

flagUp=0;

else

flagDown=0;

}

low+=flagDown;

hig+=flagUp;

}

int main(){

scanf("%d",&n);

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

scanf("%d",&map[i][j]);

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++)

if (!vis[i][j])

bfs(i,j);

printf("%d %d\n",hig,low);

return 0;

}

BZOJ 1104: [POI2007]洪水pow

并查集从小到大插入然后贪心计算答案

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=1010;
int n,m;
int father[Maxn*Maxn];
bool isSet[Maxn*Maxn];
inline void initFather(){for (int i=1;i<=n*m;i++) father[i]=i;}
inline int getFather(int x){return father[x]=(father[x]==x?x:getFather(father[x]));}
inline void mergeFather(int x,int y){
    int fx=getFather(x),fy=getFather(y);
    if (fx==fy) return;
    if (fx<fy){
        father[fx]=fy;
        isSet[fy]=isSet[fx]||isSet[fy];
    }else{
        father[fy]=fx;
        isSet[fx]=isSet[fx]||isSet[fy];
    }
}
int map[Maxn][Maxn];
int Ans;
struct Point{
    int x,y;
    int height;
    bool isKey;
    Point(){}
    Point(int x0,int y0,int height0){
        x=x0;
        y=y0;
        if (height0>=0){
            height=height0;
            isKey=true;
        }else{
            height=-height0;
            isKey=false;
        }
    }
    int index(){
        return (x-1)*m+y;
    }
};
Point li[Maxn*Maxn];
bool cmp(Point a,Point b){
    if (a.height < b.height) return true;
    return false;
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
    freopen("pow.in","r",stdin);
    freopen("pow.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            scanf("%d",&map[i][j]);
    initFather();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            li[(i-1)*m+j]=Point(i,j,map[i][j]);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (map[i][j]<0) map[i][j]=-map[i][j];
    sort(li+1,li+(n*m)+1,cmp);
    Ans=0;
    for (int i=1,j;i<=n*m;){
        j=i;
        do{
            for (int k=0;k<4;k++){
                int x=li[j].x+dx[k],y=li[j].y+dy[k];
                if (1<=x && x<=n && 1<=y && y<=m)
                    if (li[j].height>=map[x][y])
                        mergeFather(li[j].index(),(x-1)*m+y);
            }
            j++;
        }while(j<=n*m && li[j-1].height==li[j].height);
        j=i;
        do{
            if (li[j].isKey && isSet[getFather(li[j].index())]==false){
                Ans++;
                isSet[getFather(li[j].index())]=true;
            }
            j++;
        }while(j<=n*m && li[j-1].height==li[j].height);
        i=j;
    }
    printf("%d\n",Ans);
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int Maxn=1010;

int n,m;

int father[Maxn*Maxn];

bool isSet[Maxn*Maxn];

inline void initFather(){for (int i=1;i<=n*m;i++) father[i]=i;}

inline int getFather(int x){return father[x]=(father[x]==x?x:getFather(father[x]));}

inline void mergeFather(int x,int y){

int fx=getFather(x),fy=getFather(y);

if (fx==fy) return;

if (fx<fy){

father[fx]=fy;

isSet[fy]=isSet[fx]||isSet[fy];

}else{

father[fy]=fx;

isSet[fx]=isSet[fx]||isSet[fy];

}

int map[Maxn][Maxn];

int Ans;

struct Point{

int x,y;

int height;

bool isKey;

Point(){}

Point(int x0,int y0,int height0){

x=x0;

y=y0;

if (height0>=0){

height=height0;

isKey=true;

}else{

height=-height0;

isKey=false;

}

int index(){

return (x-1)*m+y;

}

};

Point li[Maxn*Maxn];

bool cmp(Point a,Point b){

if (a.height < b.height) return true;

return false;

}

int dx[]={0,1,0,-1};

int dy[]={1,0,-1,0};

int main(){

freopen("pow.in","r",stdin);

freopen("pow.out","w",stdout);

scanf("%d%d",&n,&m);

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

scanf("%d",&map[i][j]);

initFather();

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

li[(i-1)*m+j]=Point(i,j,map[i][j]);

for (int i=1;i<=n;i++)

for (int j=1;j<=m;j++)

if (map[i][j]<0) map[i][j]=-map[i][j];

sort(li+1,li+(n*m)+1,cmp);

Ans=0;

for (int i=1,j;i<=n*m;){

j=i;

do{

for (int k=0;k<4;k++){

int x=li[j].x+dx[k],y=li[j].y+dy[k];

if (1<=x && x<=n && 1<=y && y<=m)

if (li[j].height>=map[x][y])

mergeFather(li[j].index(),(x-1)*m+y);

}

j++;

}while(j<=n*m && li[j-1].height==li[j].height);

j=i;

do{

if (li[j].isKey && isSet[getFather(li[j].index())]==false){

Ans++;

isSet[getFather(li[j].index())]=true;

}

j++;

}while(j<=n*m && li[j-1].height==li[j].height);

i=j;

}

printf("%d\n",Ans);

return 0;

}

BZOJ 3747: [POI2015]Kinoman

枚举左端点，区间线段树，区间修改+单点最大值

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
const int Maxn=1000010;
struct Btree{
    long long tag;
    long long max;
    Btree(){tag=max=0;}
};
Btree tree[Maxn*4];
inline void update(int x,int left,int right){
    if (left==right) return;
    int l=x*2,r=x*2+1;
    tree[x].max=max(tree[l].max,tree[r].max);
}
inline void clean(int x,int left,int right){
    if (left==right) return;
    if (tree[x].tag!=0){
        long long tag=tree[x].tag;
        tree[x].tag=0;
        int l=x*2,r=x*2+1;
        tree[l].tag+=tag;
        tree[l].max+=tag;
        tree[r].tag+=tag;
        tree[r].max+=tag;
    }
}
void modify(int x,int l,int r,int left,int right,long long val){
    clean(x,l,r);
    if (left<=l && r<=right){
        tree[x].tag+=val;
        tree[x].max+=val;
    }else{
        int mid=(l+r)/2;
        if (left<=mid) modify(x*2,l,mid,left,right,val);
        if (mid<right) modify(x*2+1,mid+1,r,left,right,val);
        update(x,l,r);
    }
}
long long query(int x,int l,int r,int left,int right){
    clean(x,l,r);
    if (left<=l && r<=right){
        return tree[x].max;
    }else{
        int mid=(l+r)/2;
        long long ret=0;
        if (left<=mid) ret=max(ret,query(x*2,l,mid,left,right));
        if (mid<right) ret=max(ret,query(x*2+1,mid+1,r,left,right));
        return ret;
    }
}
int n,m;
int f[Maxn];
long long w[Maxn];
int nxt[Maxn];
int loc[Maxn];
long long Ans=0;
inline int read(){
    int x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
inline long long readLL(){
    long long x=0;char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int main(){
    n=read();m=read();
    for (int i=1;i<=n;i++) f[i]=read();
    for (int i=1;i<=m;i++) w[i]=readLL();
    for (int i=n;i>=1;i--){
        nxt[i]=loc[f[i]];
        loc[f[i]]=i;
    }
    for (int i=1;i<=m;i++)
        if (loc[i])
            modify(1,1,n,loc[i],(nxt[loc[i]]!=0?nxt[loc[i]]-1:n),w[i]);
    Ans=tree[1].max;
    for (int i=1;i<n;i++){
        modify(1,1,n,i,(nxt[i]!=0?nxt[i]-1:n),-w[f[i]]);
        if (nxt[i]!=0)
            modify(1,1,n,nxt[i],(nxt[nxt[i]]!=0?nxt[nxt[i]]-1:n),w[f[i]]);
        Ans=max(Ans,tree[1].max);
    }
    cout<<Ans<<endl;
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<string>

#include<cstring>

using namespace std;

const int Maxn=1000010;

struct Btree{

long long tag;

long long max;

Btree(){tag=max=0;}

};

Btree tree[Maxn*4];

inline void update(int x,int left,int right){

if (left==right) return;

int l=x*2,r=x*2+1;

tree[x].max=max(tree[l].max,tree[r].max);

}

inline void clean(int x,int left,int right){

if (left==right) return;

if (tree[x].tag!=0){

long long tag=tree[x].tag;

tree[x].tag=0;

int l=x*2,r=x*2+1;

tree[l].tag+=tag;

tree[l].max+=tag;

tree[r].tag+=tag;

tree[r].max+=tag;

}

void modify(int x,int l,int r,int left,int right,long long val){

clean(x,l,r);

if (left<=l && r<=right){

tree[x].tag+=val;

tree[x].max+=val;

}else{

int mid=(l+r)/2;

if (left<=mid) modify(x*2,l,mid,left,right,val);

if (mid<right) modify(x*2+1,mid+1,r,left,right,val);

update(x,l,r);

}

long long query(int x,int l,int r,int left,int right){

clean(x,l,r);

if (left<=l && r<=right){

return tree[x].max;

}else{

int mid=(l+r)/2;

long long ret=0;

if (left<=mid) ret=max(ret,query(x*2,l,mid,left,right));

if (mid<right) ret=max(ret,query(x*2+1,mid+1,r,left,right));

return ret;

}

int n,m;

int f[Maxn];

long long w[Maxn];

int nxt[Maxn];

int loc[Maxn];

long long Ans=0;

inline int read(){

int x=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

inline long long readLL(){

long long x=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

int main(){

n=read();m=read();

for (int i=1;i<=n;i++) f[i]=read();

for (int i=1;i<=m;i++) w[i]=readLL();

for (int i=n;i>=1;i--){

nxt[i]=loc[f[i]];

loc[f[i]]=i;

}

for (int i=1;i<=m;i++)

if (loc[i])

modify(1,1,n,loc[i],(nxt[loc[i]]!=0?nxt[loc[i]]-1:n),w[i]);

Ans=tree[1].max;

for (int i=1;i<n;i++){

modify(1,1,n,i,(nxt[i]!=0?nxt[i]-1:n),-w[f[i]]);

if (nxt[i]!=0)

modify(1,1,n,nxt[i],(nxt[nxt[i]]!=0?nxt[nxt[i]]-1:n),w[f[i]]);

Ans=max(Ans,tree[1].max);

}

cout<<Ans<<endl;

return 0;

}

WNJXYKの博客

喂你脚下有坑