Starry

发表于 更新于 分类于 本文字数： 350 阅读时长 ≈ 1 分钟

调了一下午，注意k为0时候下标会偏移都后一个。

贪的时候，x为整数显然是贪连续k，负数则贪心放置于头尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll tt,n,k,x,a[(int)2e5+9],dp[(int)2e5+9],sum[(int)2e5+9];

void solve(){
    cin>>n>>k>>x;
    f(i,1,n)cin>>a[i];
    multiset<ll> s;
    s.insert(0);
    for(int i=1;i<=n;++i)sum[i]=sum[i-1]+a[i]-x;
    ll ans=0;
    for(int i=1;i<=n;++i){
        for(int j=max(i-k+1ll,1ll);j<=i;++j){
            ll sz=i-j+1ll;
            ll qsb=max(2ll*x*sz,max(0ll,k-(n-sz))*2ll*x);
            ans=max(ans,sum[i]-sum[j-1]+qsb);
        }
        if(i>=k){
            ll sz=max(0ll,k-(n-i));
            ll qsb=max(2ll*x*k,2ll*sz*x);
            ans=max(ans,sum[i]-*s.begin()+qsb);

            ll mi=max(k-1ll,0ll);
            s.insert(sum[i-mi]);
            ll msz=min(((ll)s.size())-1,sz);
            s.erase(s.find(0));
            for(int j=1;j<=msz;++j){
                ans=max(ans,sum[i]-*s.begin()+2ll*(sz-j)*x);
                auto it=s.find(sum[j]);
                s.erase(it);
            }
            s.insert(0);
            for(int j=1;j<=msz;++j)s.insert(sum[j]);
            
        }
    }
    cout<<ans<<"\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>tt;
    f(sb,1,tt){
        solve();
    }
    return 0;
}

发表于 更新于 分类于 本文字数： 305 阅读时长 ≈ 1 分钟

补完发现自己就是个弱智东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

ll n,p[(int)2e5+9],q[(int)2e5+9],ans=1,l,r;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;++i)cin>>x,p[x]=i;
    for(int i=1,x;i<=n;++i)cin>>x,q[x]=i;
    
    l=min(p[1],q[1]),r=max(p[1],q[1]);
	if(l>1)ans+=(l-1)*(l)/2ll;
	if(r<n)ans+=(n-r)*(n-r+1)/2ll;
	if(l!=r)ans+=(r-l-1)*(r-l)/2ll;
    for(int i=1;i<n;++i){
    	l=min({l,q[i],p[i]}),r=max({r,q[i],p[i]});
    	if((p[i+1]<=r&&p[i+1]>=l)||(q[i+1]<=r&&q[i+1]>=l))continue;
    	ll L=0,R=n+1ll;
    	if(p[i+1]<=l)L=max(L,p[i+1]);
    	if(p[i+1]>=r)R=min(R,p[i+1]);
    	if(q[i+1]>=r)R=min(R,q[i+1]);
    	if(q[i+1]<=l)L=max(L,q[i+1]);
    	ans+=(l-L)*(R-r);
    }
    cout<<ans;
    return 0;
}

发表于 更新于 分类于 本文字数： 393 阅读时长 ≈ 1 分钟

将式子拆分成四个查询，注意下标会访问到0，而且当时的答案是0，所以不妨初始化成这样，不然会计算出错的贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;
using a4=array<int,4>;

ll n,q,a[(int)5e4+9],cnt[2][(int)5e4+9],res,ans[(int)5e4+9],belong[(int)5e4+9],fk,l,r; 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<a4>v;
    cin>>q;
	for(int i=1,x,y,z,w;i<=q;++i){
		cin>>x>>y>>z>>w;
		v.push_back({min(w,y),max(w,y),i,1});
		v.push_back({min(x-1,z-1),max(x-1,z-1),i,1});
		v.push_back({min(x-1,w),max(x-1,w),i,-1});
		v.push_back({min(z-1,y),max(z-1,y),i,-1});
	}
	fk=ceil(n/sqrt(4.0*q));
	for(int i=1;i<=n;++i)belong[i]=(i-1)/fk+1;
	sort(all(v),[](const a4& aa,const a4& bb){return belong[aa[0]]==belong[bb[0]]?(belong[aa[0]]&1)^(aa[1]>bb[1]):belong[aa[0]]<belong[bb[0]];});
	
	for(auto &&[aa,bb,cc,dd]:v){
		while(l>aa)cnt[0][a[l]]-=1,res-=cnt[1][a[l]],l-=1;
		while(r<bb)cnt[1][a[++r]]+=1,res+=cnt[0][a[r]];
		while(l<aa)cnt[0][a[++l]]+=1,res+=cnt[1][a[l]];
		while(r>bb)cnt[1][a[r]]-=1,res-=cnt[0][a[r]],r-=1;
		ans[cc]+=1ll*dd*res;
	}
	for(int i=1;i<=q;++i)cout<<ans[i]<<"\n";
	
    return 0;
}

发表于 更新于 本文字数： 276 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;
using a3=std::array<int,3>;

ll n,q,a[(int)1e5+9],cnt[(int)1e5+9],l=1,r,belong[(int)1e5+9],fk,ans[(int)1e5+9],sum; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;++i)cin>>a[i];
    fk=ceil(n/sqrt(q));
	for(int i=1;i<=n;++i)belong[i]=(i-1)/fk+1;
	vector<a3> v;
	for(int i=1,x,y;i<=q;++i){
		cin>>x>>y;
		v.push_back({x,y,i});
	}
	sort(all(v),[](const a3& aa,const a3& bb){return belong[aa[0]]==belong[bb[0]]?(belong[aa[0]]&1)^(aa[1]>bb[1]):belong[aa[0]]<belong[bb[0]];});

	for(auto &&[aa,bb,cc]:v){
		while(l>aa)sum+=(++cnt[a[--l]]==1);
		while(r<bb)sum+=(++cnt[a[++r]]==1);
		while(l<aa)sum-=(--cnt[a[l++]]==0);
		while(r>bb)sum-=(--cnt[a[r--]]==0);
		ans[cc]=sum==bb-aa+1;
	}
	for(int i=1;i<=q;++i)cout<<(ans[i]?"Yes\n":"No\n");
    return 0;
}

发表于 更新于 分类于 本文字数： 408 阅读时长 ≈ 1 分钟

好像之前位置的写法是错误的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;
using a4=std::array<int,4>;

char opt;
int n,m,tot=1,a[(int)2e5+9],fk,belong[(int)2e5+9],l=1,r,cnt[(int)1e6+9],ans,now=1,res[(int)2e5+9];
struct{
	int pos,val;
}modify[(int)2e5+9];



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    vector<a4> q;
    for(int i=1,x,y;i<=m;++i){
    	cin>>opt>>x>>y;
    	if(opt=='Q'){
    		q.push_back({x,y,tot,i});
    	}else {
    		modify[++tot]={x,y};
    	}
    }
    fk=ceil(pow(n,2.0/3.0)*pow(tot,1.0/3.0)/pow(m,1.0/3.0));
    for(int i=1;i<=n;++i)belong[i]=(i-1)/fk+1;
    sort(all(q),[](const a4 &aa,const a4 &bb){
    	if(belong[aa[0]]!=belong[bb[0]])return belong[aa[0]]<belong[bb[0]];
    	if(belong[aa[1]]!=belong[bb[1]])return belong[aa[0]]&1?aa[1]<bb[1]:aa[1]>bb[1];
    	return aa[2]<bb[2];
    });
	
	for(auto [aa,bb,cc,dd]:q){
		while(l>aa)ans+=(++cnt[a[--l]]==1);
		while(r<bb)ans+=(++cnt[a[++r]]==1);
		while(l<aa)ans-=(--cnt[a[l++]]==0);
		while(r>bb)ans-=(--cnt[a[r--]]==0);
		while(now<cc){
			now+=1;
			if(modify[now].pos>=aa&&modify[now].pos<=bb){ans-=(--cnt[a[modify[now].pos]]==0);ans+=(++cnt[modify[now].val]==1);}
			swap(modify[now].val,a[modify[now].pos]);
		}
		while(now>cc){
			if(modify[now].pos>=aa&&modify[now].pos<=bb){ans-=(--cnt[a[modify[now].pos]]==0);ans+=(++cnt[modify[now].val]==1);}
			swap(modify[now].val,a[modify[now].pos]);
			now-=1;
		}
		res[dd]=ans;
	}

	for(int i=1;i<=m;++i)if(res[i])cout<<res[i]<<"\n";
    return 0;
}
0%