QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #647081 | #7434. 冷たい部屋、一人 | piggy123 | WA | 9ms | 103968kb | C++14 | 6.8kb | 2024-10-17 11:31:38 | 2024-10-17 11:31:39 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a[500005],b[21][500005],c[21][500005],lg[500005],ans[500005],n,m;
struct qry {
ll l,r,id;
} p[500005],p2[500005];
vector<ll> col[500005],CC[500005];
const ll S=0;
ll S2=0;
struct block {
const ll B=800;
ll tag[805],z[500005];
void add(ll pos,ll v) {
z[pos]+=v;
tag[(pos-1)/B+1]+=v;
}
ll query(ll pos) {
ll v=(pos-1)/B+1,r=(n-1)/B+1,ans=0;
for (ll i=v+1; i<=r; i++)ans+=tag[i];
for (ll i=pos; i<=v*B; i++)ans+=z[i];
return ans;
}
} B;
ll getmx(ll l,ll r) {
ll k=lg[r-l+1];
return max(c[k][l],c[k][r-(1ll<<k)+1]);
}
ll getmi(ll l,ll r) {
ll k=lg[r-l+1];
return min(b[k][l],b[k][r-(1ll<<k)+1]);
}
ll v[1000005],cnt[1000005],d[1000005],nxt[1000005],to[1000005],T;
vector<qry> Q[1000005];
struct CHAIN{
ll vis[1000005],sz[1000005],ano[1000005];
array<ll,5> stk[1000005];
ll top,gx;
void init(ll len){
for (ll i=0;i<=len;i++)vis[i]=0,sz[i]=1,ano[i]=i;
top=0,gx=0;
}
void link(ll a){
ll l=ano[a],r=ano[a+1];
ano[l]=r,ano[r]=l;
stk[++top]={l,r,a,sz[a],sz[a+1]};
gx+=sz[a]*sz[a+1];
sz[l]=sz[r]=sz[a]+sz[a+1];
// cout<<"?" <<a<<" "<< sz[a]<<" "<<sz[a+1]<<"\n";
}
void add(ll pos){
vis[d[pos]]++;
if (vis[d[pos]]==2){
link(d[pos]);
}
}
void del(ll pos){
vis[d[pos]]--;
if (vis[d[pos]]==1){
redo();
}
}
void redo(){
auto tp=stk[top--];
gx-=tp[3]*tp[4];
ano[tp[0]]=tp[2];
ano[tp[1]]=tp[2]+1;
sz[tp[0]]=tp[3];
sz[tp[1]]=tp[4];
}
}C;
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
for (ll i=1; i<=n; i++) {
cin >> a[i];
col[a[i]].push_back(i);
}
for (ll i=1; i<=n; i++) {
if (i>1)lg[i]=lg[i>>1]+1;
cin >> b[0][i];
c[0][i]=b[0][i];
}
for (ll i=1; i<=20; i++) {
for (ll j=1; j+(1ll<<i)-1<=n; j++) {
b[i][j]=min(b[i-1][j],b[i-1][j+(1ll<<(i-1))]);
c[i][j]=max(c[i-1][j],c[i-1][j+(1ll<<(i-1))]);
}
}
for (ll i=1; i<=m; i++) {
cin >> p[i].l >> p[i].r;
p[i].id=i;
}
for (ll i=1; i<=n; i++) {
if (col[i].size()<=S) {
for (ll j=0; j<(ll)col[i].size(); j++) {
for (ll k=j+1; k<(ll)col[i].size(); k++) {
ll mi=getmi(col[i][j],col[i][k]),mx=getmx(col[i][j],col[i][k]);
CC[mx].push_back(mi);
}
}
}
}
sort(p+1,p+1+m,[](qry a,qry b) {
return a.r<b.r;
});
ll ps=0;
for (ll i=1; i<=m; i++) {
while (ps+1<=n&&ps+1<=p[i].r) {
for (ll j:CC[ps+1]) {
B.add(j,1);
}
ps++;
}
ans[p[i].id]+=B.query(p[i].l);
}
for (ll i=1; i<=n; i++) {
if (col[i].size()>S) {
T=i;
ll N=col[i].size();
vector<ll> book;
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
book.push_back(mi);
book.push_back(mx);
}
sort(book.begin(),book.end());
book.erase(unique(book.begin(),book.end()),book.end());
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
++cnt[lower_bound(book.begin(),book.end(),mi)-book.begin()+1];
++cnt[lower_bound(book.begin(),book.end(),mx)-book.begin()+1];
}
for (ll j=1; j<=(ll)book.size(); j++)cnt[j]+=cnt[j-1];
ll lim=cnt[book.size()];
for (ll j=0; j+1<N; j++) {
ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
ll mip=lower_bound(book.begin(),book.end(),mi)-book.begin()+1;
ll mxp=lower_bound(book.begin(),book.end(),mx)-book.begin()+1;
d[cnt[mip]--]=j;
to[cnt[mip]+1]=mi;
d[cnt[mxp]--]=j;
to[cnt[mxp]+1]=mx;
}
ll ps=0;
for (ll j=1; j<=n; j++) {
while (ps+1<=lim&&to[ps+1]<=j)ps++;
nxt[j]=ps;
}
S2=2*N/sqrt(m)+1;
// cout<<"! "<< i<<"\n";
for (ll j=1; j<=m; j++) {
p2[j].l=nxt[p[j].l-1]+1,p2[j].r=nxt[p[j].r],p2[j].id=p[j].id;
if ((p2[j].l-1)/S2==(p2[j].r-1)/S2) {
C.init(lim);
for (ll k=p2[j].l; k<=p2[j].r; k++) {
C.add(k);
}
ans[p2[j].id]+=C.gx;
// cout<< p2[j].id<<":"<<C.gx<<"\n";
} else {
Q[(p2[j].l-1)/S2+1].push_back(p2[j]);
}
}
for (ll j=1; j<=(lim-1)/S2+1; j++) {
if (!Q[j].size())continue;
ll lb=j*S2;
C.init(lim);
ll L=lb+1,R=lb;
for (qry k:Q[j]) {
while (R<k.r)C.add(++R);
while (L>k.l)C.add(--L);
ans[k.id]+=C.gx;
while (L<lb+1)C.del(L++);
}
}
for (ll j=0; j<=lim; j++)cnt[j]=to[j]=nxt[j]=d[j]=0,Q[j].clear();
}
}
for (ll i=1; i<=m; i++) {
cout<< ans[i]<<"\n";
}
return 0;
}
/*
■■■■■ ■■ ■■■ ■■■ ■ ■ ■ ■■■■ ■■■■
■ ■■ ■■ ■ ■■ ■ ■■ ■ ■ ■■ ■ ■■ ■■ ■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■■ ■■ ■■ ■ ■■
■ ■ ■■ ■ ■ ■ ■ ■ ■ ■■ ■ ■■ ■■
■ ■ ■■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■■ ■ ■■■ ■ ■■■ ■■ ■■ ■■ ■■■
■■■■■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■■ ■
■ ■■ ■ ■ ■ ■ ■■ ■■ ■ ■ ■■
■ ■■ ■■ ■■ ■■ ■■ ■■ ■■ ■ ■■ ■■
■ ■■ ■■■■ ■■■■ ■■ ■■ ■■■■■■ ■■■■
*/
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 101884kb
input:
100 100 4 1 5 1 2 1 7 5 3 7 2 3 6 6 5 3 2 2 4 1 6 5 6 2 2 2 7 6 1 3 6 3 5 6 7 6 1 2 3 3 4 2 1 1 5 4 4 3 6 7 1 1 6 1 5 6 2 3 7 4 2 4 6 7 7 3 5 3 7 2 3 3 5 1 4 7 1 2 2 5 2 2 4 3 4 7 2 7 7 3 7 3 6 6 5 4 5 4 7 6 93 52 12 70 25 36 18 37 27 99 68 40 84 3 76 57 60 19 33 41 92 87 58 13 15 43 28 63 64 59 31 ...
output:
1 0 13 71 1 1 3 7 0 0 2 1 3 20 12 6 61 24 1 0 0 2 3 19 0 0 6 2 0 0 4 1 135 0 19 1 1 29 14 39 1 0 1 7 7 0 12 3 0 1 0 1 1 5 0 28 14 19 2 1 0 0 6 5 0 0 2 7 5 1 2 2 0 1 11 1 0 1 0 10 0 0 5 1 33 1 17 2 1 22 20 1 2 0 0 16 0 1 1 15
result:
ok 100 numbers
Test #2:
score: -100
Wrong Answer
time: 9ms
memory: 103968kb
input:
100 100 8 8 2 8 8 12 11 8 5 5 5 1 7 6 6 11 3 13 1 12 2 2 4 1 11 13 10 7 1 2 4 3 1 12 1 5 13 8 1 5 12 5 12 4 6 3 5 4 8 3 4 1 4 3 9 2 11 9 4 8 12 3 5 13 13 1 9 12 2 13 8 13 4 13 12 5 12 13 2 6 4 4 1 6 6 9 12 7 4 3 10 7 1 7 7 10 4 12 3 9 96 87 12 73 74 78 99 76 7 77 54 88 90 86 95 94 31 83 27 11 66 91 ...
output:
1 6 3 0 1 1 16 1 1 10 7 9 2 8 2 1 3 5 0 7 2 2 2 0 2 1 7 0 0 1 108 1 0 0 6 4 1 0 3 13 1 3 0 10 0 0 2 21 0 18 0 11 0 8 13 9 0 0 0 11 12 2 2 0 3 16 1 7 1 16 0 2 3 7 0 2 10 2 4 2 6 0 0 6 3 1 0 0 5 7 0 0 6 0 7 0 4 0 3 0
result:
wrong answer 1st numbers differ - expected: '0', found: '1'