送花

我们移动右端点，之后我们用线段树维护全局最大值。

之后还要记录上次的位置和上上次的位置。

之后每次加和减。



#include<bits/stdc++.h>

using std::cout; using std::endl;

#define try(i,a,b) for(register signed i=a;i<=b;++i)

#define throw(i,a,b) for(register signed i=a;i>=b;--i)

#define asm(i,x) for(register signed i=head[x];i;i=edge[i].next)

namespace xin_io

{

	#define debug cout<<"debug"<<endl

	#define enum(x) cout<<#x" = "<<x<<endl;

	#define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++

	char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull;

	class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x)

	{

		register type s = 0; register int f = 1; register char ch = gc();

		while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}

		while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch  xor 48),ch = gc(); return x = s * f,*this;

	}}io;

}

using namespace xin_io; static const int maxn = 5e6+10,inf = 1e9+7,mod = 998244353; const ll llinf = 1e18+7;

#define int long long

namespace xin

{

	int lst1[maxn],lst2[maxn];

	class xin_seg

	{

		private:

			#define ls(fa) (fa << 1)

			#define rs(fa) (fa << 1 | 1)

			inline void up(int fa) {t[fa].s = std::max(t[ls(fa)].s , t[rs(fa)].s);}

			inline void down(int fa)

			{

				if(!t[fa].debt) return ;

				t[ls(fa)].s += t[fa].debt ; t[rs(fa)].s += t[fa].debt;

				t[ls(fa)].debt += t[fa].debt ; t[rs(fa)].debt += t[fa].debt;

				t[fa].debt = 0;

			}

		public:

			class xin_tree{public:int s,debt;}t[maxn];

			void update(int fa,int l,int r,int ql,int qr,int val)

			{

				if(ql <= l and qr >= r)

				{

					t[fa].s += val;

					t[fa].debt += val;

					return ;

				}

				register int mid = l + r >> 1;

				down(fa);

				if(ql <= mid) update(ls(fa),l,mid,ql,qr,val);

				if(qr >  mid) update(rs(fa),mid+1,r,ql,qr,val);

				up(fa);

			}

	}t;

	int n,c[maxn],d[maxn],m;

	int ans = -inf;

	inline short main()

	{

		io >> n >> m;

		try(i,1,n) io >> c[i];

		try(i,1,m) io >> d[i];

		try(i,1,n)

		{

//			cout<<"i = "<<i<<" c[i] = "<<c[i]<<" lst1[c[i]] = "<<lst1[c[i]]<<" lst2[c[i]] = "<<lst2[c[i]]<<endl;

			if(!lst1[c[i]] and !lst2[c[i]]) t.update(1,1,n,1,i,d[c[i]]);

			else if(lst1[c[i]] and !lst2[c[i]]) t.update(1,1,n,lst1[c[i]]+1,i,d[c[i]]),t.update(1,1,n,1,lst1[c[i]],-d[c[i]]);

			else t.update(1,1,n,lst2[c[i]]+1,lst1[c[i]],-d[c[i]]),t.update(1,1,n,lst1[c[i]]+1,i,d[c[i]]);

			ans = std::max(ans,t.t[1].s);

//			enum(t.t[1].s);

			lst2[c[i]] = lst1[c[i]];

			lst1[c[i]] = i;

		}

		cout<<ans<<endl;

		return 0;

	}

}

signed main() {return xin::main();}

巴特西

[考试总结]noip模拟40

送花

最新文章

热门文章