列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[lose]

题目简述：
在指定区间抓取总合不大于 S 的元素集合，而集合大小越大越好

题目分析：
对于区间[L，R]很明显地，从小排到大，依序挑入即可，照贪婪的思路。
但没办法对每个询问区间进行排序，因此使用归并树。
将合并排序的每个过程记录下来，然后二分边界数值。
小心，等价的边界数值要特别处理。
可能不是这个解法，速度稍慢了些。

AC(3.7s, 10.8MB) judge by this@ZeroJudge 

代碼: [選擇]

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
short ST[20][100010];
int AST[20][100010];
void build(int dep, int l, int r) {
    if(l < r) {
        int m = (l+r)/2, i;
        memcpy(ST[dep+1]+l, ST[dep]+l, (r-l+1)*2);
        build(dep+1, l, m);
        build(dep+1, m+1, r);
        int idx1 = l, idx2 = m+1, top = l, tmp = 0;
        while(idx1 <= m && idx2 <= r) {
            if(ST[dep+1][idx1] < ST[dep+1][idx2])
                ST[dep][top] = ST[dep+1][idx1++];
            else
                ST[dep][top] = ST[dep+1][idx2++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
        while(idx1 <= m) {
            ST[dep][top] = ST[dep+1][idx1++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
        while(idx2 <= r) {
            ST[dep][top] = ST[dep+1][idx2++];
            tmp += ST[dep][top];
            AST[dep][top++] = tmp;
        }
    }
    if(l == r)
        AST[dep][l] = ST[dep][l];
}
int L, R, S;
int key, Count, cost, same;
void query(int dep, int l, int r, int ql, int qr) {
    if(cost > S)   return ;
    if(l == ql && r == qr) {
        int ff = upper_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
        int gg = lower_bound(ST[dep]+l, ST[dep]+r+1, key)-(ST[dep]+l);
        same += ff-gg;
        if(gg) {
            Count += gg;
            cost += AST[dep][gg+l-1];
        }
        return;
    }
    int m = (l+r)/2;
    if(m >= qr)
        query(dep+1, l, m, ql, qr);
    else if(m < ql)
        query(dep+1, m+1, r, ql, qr);
    else {
        query(dep+1, l, m, ql, m);
        query(dep+1, m+1, r, m+1, qr);
    }
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
    int t;
    int n, q, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &q);
        for(i = 1; i <= n; i++) {
            //scanf("%d", &ST[0][i]);
            ReadInt(&j);
            ST[0][i] = j;
        }
        build(0, 1, n);
        int ans = 0;
        ST[0][0] = 0;
        for(i = 1; i <= q; i++) {
            //scanf("%d %d %d", &L, &R, &S);
            ReadInt(&L);
            ReadInt(&R);
            ReadInt(&S);
            int l = 0, r = n, m;
            int x = 0;
            while(l <= r) {
                m = (l+r)/2;
                key = ST[0][m], Count = 0, cost = 0, same = 0;
                query(0, 1, n, L, R);
                if(cost <= S) {
                    l = m+1;
                    if(key)
                        Count += min((S-cost)/key, same);
                    if(Count > x)   x = Count;
                } else
                    r = m-1;
            }
            ans ^= x+i;
        }
        printf("%d\n", ans);
    }
    return 0;
}


[jacky860226]

有一種資料結構稱為劃分樹
儲存了快速排序的過程
可以在logn的時間內取得區間第K大
而這題亦可用持久性線段樹維護(等我co完後會補上代碼)

代碼: [選擇]

#include<bits/stdc++.h>
using namespace std;
int t,n,q;
int s[100005];
int tre[25][100005];
int add[25][100005];
int tol[25][100005];
int a,b,c;
void build(int l,int r,int d){
if(l==r)return;
int m=(l+r)>>1;
int same=m-l+1;
int nl=l,nr=m+1;
for(int i=l;i<=r;i++)if(tre[d][i]<s[m])same--;
for(int i=l;i<=r;i++){
if(tre[d][i]<s[m]){
tre[d+1][nl++]=tre[d][i];
add[d][i]+=tre[d][i];
tol[d][i]++;
}else if(tre[d][i]==s[m]&&same){
tre[d+1][nl++]=tre[d][i];
add[d][i]+=tre[d][i];
tol[d][i]++;
same--;
}else{
tre[d+1][nr++]=tre[d][i];
}
tol[d][i]+=tol[d][i-1];
add[d][i]+=add[d][i-1];
}
build(l,m,d+1);build(m+1,r,d+1);
}
int find(int L,int R,int l,int r,int d,int k){
if(L==R)return tre[d][L];
int cn=tol[d][r]-tol[d][l-1];
int m=(L+R)>>1;
if(cn>=k){
int nl=L+tol[d][l-1]-tol[d][L-1];
int nr=nl+cn-1;
return find(L,m,nl,nr,d+1,k);
}else{
int nr=r+tol[d][R]-tol[d][r];
int nl=nr-(r-l-cn);
return add[d][r]-add[d][l-1]+find(m+1,R,nl,nr,d+1,k-cn);
}
}
int search(int l,int r,int c){
while(l<=r){
int m=(l+r)>>1;
int tmd=find(1,n,a,b,0,m);
if(tmd<=c&&(m==n||find(1,n,a,b,0,m+1)>c))return m;
if(tmd<=c){
l=m+1;
}else r=m-1;
}
if(l==0)return 0;
else return r;
}
int main(){
scanf("%d",&t);
while(t--){
memset(tol,0,sizeof(tol));
memset(add,0,sizeof(add));
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
}
for(int i=1;i<=n;i++)tre[0][i]=s[i];
sort(s+1,s+1+n);
build(1,n,0);
int ans=0;
for(int i=1;i<=q;i++){
scanf("%d%d%d",&a,&b,&c);
ans^=search(0,b-a+1,c)+i;
//printf("%d\n",search(0,b-a+1,c));
}
printf("%d\n",ans);
}
return 0;
}


[jacky860226]

主席樹，是一種持久化線段樹
可以保存線段樹的歷史版本
因為所有飲料價格<=10000所以不需離散
先開一棵0~10000區間的線段樹
將每次執行插入後得到的新線段樹根節點保存在root陣列
因為是對值域進行維護，所以root[r]-root[l-1]就會是l~r區間
zerojudge 0.6s

代碼: [選擇]

#include<bits/stdc++.h>
#define N 10000
using namespace std;
int t,n,m;
struct node{
node *l,*r;
int cnt,id,sum;
inline void init(){
l=r=NULL;
sum=cnt=id=0;
}
inline void up(){
sum=cnt=0;
if(l)cnt+=l->cnt,sum+=l->sum;
if(r)cnt+=r->cnt,sum+=r->sum;
}
}u[2000005];
int use;
int s[100005];
node *root[100005];
node *build(int l,int r){
node *p=&u[use++];
p->init();
if(l==r){
p->id=l;
}else{
int mid=(l+r)>>1;
p->l=build(l,mid);
p->r=build(mid+1,r);
}
return p;
}
node *insert(int l,int r,node *d,int x){
if(x<l||r<x)return d;
node *p=&u[use++];
*p=*d;
if(l==r){
p->sum+=p->id;
p->cnt++;
}else{
int mid=(l+r)>>1;
p->l=insert(l,mid,d->l,x);
p->r=insert(mid+1,r,d->r,x);
p->up();
}
return p;
}
int find(int l,int r,node *a,node *b,int cnt,int k){
if(l==r){
if(b->sum-a->sum<=k)return b->cnt-a->cnt+cnt;
else return cnt+k/a->id;
}
int mid=(l+r)>>1;
if(b->l->sum-a->l->sum>=k)return find(l,mid,a->l,b->l,cnt,k);
else return find(mid+1,r,a->r,b->r,cnt+b->l->cnt-a->l->cnt,k-(b->l->sum-a->l->sum));
}
int a,b,c,tu;
int ans;
int main(){
scanf("%d",&t);
root[0]=build(0,N);
tu=use;
while(t--){
scanf("%d%d",&n,&m);
use=tu;
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
root[i]=insert(0,N,root[i-1],s[i]);
}
ans=0;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
//printf("..%d\n",find(0,N,root[a-1],root[b],0,c));
ans^=find(0,N,root[a-1],root[b],0,c)+i;
}
printf("%d\n",ans);
}
return 0;
}


[a00012025]

做法跟樓上一樣，不過可持久化線段樹是用陣列做的，不是用指標。
Zerojudge 0.8s

代碼: [選擇]

#include<stdio.h>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn=10000+10,maxm=2000000 ;
int left[maxm],right[maxm],root[100010] ;
int cnt,size[maxm] ;
LL sum[maxm] ;

void build_ST(int l,int r,int id)
{
    if(l==r) {size[id]=0 ; sum[id]=0LL ; return ; }
    left[id]=++cnt ; right[id]=++cnt ;
    int mid=(l+r)/2 ;
    build_ST(l,mid,left[id]) ;
    build_ST(mid+1,r,right[id]) ;
    size[id]=0 ; sum[id]=0LL ;
}

void tree_insert(int l,int r,int old,int newp,int pos)
{
    if(l==r) {size[newp]=size[old]+1 ; sum[newp]=sum[old]+(LL)pos ; return ; }
    int mid=(l+r)/2 ;
    if(pos<=mid)
    {
        left[newp]=++cnt ; right[newp]=right[old] ;
        tree_insert(l,mid,left[old],left[newp],pos) ;
    }
    else
    {
        right[newp]=++cnt ; left[newp]=left[old] ;
        tree_insert(mid+1,r,right[old],right[newp],pos) ;
    }
    size[newp]=size[left[newp]]+size[right[newp]] ;
    sum[newp]=sum[left[newp]]+sum[right[newp]] ;
}

int query(int l,int r,int id1,int id2,LL cost)
{
    if(l==r) return l==0 ? (size[id2]-size[id1]) : min((LL)size[id2]-size[id1],cost/l) ;
    int mid=(l+r)/2 ;
    LL lsum=sum[left[id2]]-sum[left[id1]] ;
    if(cost<lsum) return query(l,mid,left[id1],left[id2],cost) ;
    else return size[left[id2]]-size[left[id1]]+query(mid+1,r,right[id1],right[id2],cost-lsum) ;
}

int a[100010] ;
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        int n,q ; scanf("%d%d",&n,&q) ;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
        cnt=0 ;
        root[0]=++cnt ; build_ST(0,maxn,root[0]) ;
        for(int i=1;i<=n;i++)
        {
            root[i]=++cnt ;
            tree_insert(0,maxn,root[i-1],root[i],a[i]) ;
        }
        LL ANS=0LL ;
        for(int i=1;i<=q;i++)
        {
            int L,R ; LL cost ;
            scanf("%d%d%lld",&L,&R,&cost) ;
            int ans=query(0,maxn,root[L-1],root[R],cost) ;
            //printf("%d\n",ans) ;
            ANS ^= (ans+i) ;
        }
        printf("%lld\n",ANS) ;
    }
}


[ggh93234999]

跟樓上作法有點像~~
一樣用可持久化線段樹
第 1 測資點(100%): AC (0.6s, 54.1MB)

代碼: [選擇]

#include <cstdio>
#include <queue>
#include <cstdlib>
using namespace std;
struct XDD{
    int sum,adsum;
    int l,r;
    XDD(){
        sum=0; adsum=0; l=r=-1;
    }
}no[3500005];
void build(int l,int r,int now);
void go(int l,int r,int now,int lnow);
void find(int l,int r,int now,int lnow);
int tmp,head[100005],ntp=2,ori,ans,aa;
int main(){
    int T,n,i,q,a,b;
    scanf("%d",&T);
    head[0]=1;
    build(0,10005,1);
    ori=ntp;
    while(T--){
        ntp=ori;
        scanf("%d %d",&n,&q);
        for(i=1;i<=n;i++){
            scanf("%d",&tmp);
            head[i]=ntp++;
            go(0,10005,head[i],head[i-1]);
        }
        int realans=0;
        for(i=1;i<=q;i++){
            ans=0;
            scanf("%d %d %d",&a,&b,&tmp);
            aa=tmp;
            find(0,10005,head[b],head[a-1]);
            realans^=ans+i;
        }
        printf("%d\n",realans);
    }
}
void build(int l,int r,int now){
    if(l!=r){
        no[now].l=ntp++; no[now].r=ntp++;
        int mid=(l+r)>>1;
        build(l,mid,no[now].l);
        build(mid+1,r,no[now].r);
    }
}
void go(int l,int r,int now,int lnow){
    no[now]=no[lnow];
    if(l==r && l==tmp){
        no[now].sum++; no[now].adsum+=tmp;
        no[now].l=no[now].r=-1;
        return ;
    }
    if(l<= tmp && tmp <= r){
        no[now].sum++; no[now].adsum+=tmp;
        int mid=(l+r)>>1;
        no[now].l=ntp++; no[now].r=ntp++;
        go(l,mid,no[now].l,no[lnow].l);
        go(mid+1,r,no[now].r,no[lnow].r);
        return ;
    }
}
void find(int l,int r,int now,int lnow){
    if(l==r){
        int xx=aa/l;
        ans+=xx;
        return;
    }
    int xl=no[now].l,xr=no[now].r,yl=no[lnow].l,yr=no[lnow].r;
    if(no[now].adsum-no[lnow].adsum<=aa){
        aa-=(no[now].adsum-no[lnow].adsum);
        ans+=(no[now].sum-no[lnow].sum);
    }
    else if(no[xl].adsum-no[yl].adsum<=aa){
        aa-=(no[xl].adsum-no[yl].adsum);
        ans+=(no[xl].sum-no[yl].sum);
        int mid=(l+r)>>1;
        find(mid+1,r,xr,yr);
    }
    else{
        int mid=(l+r)>>1;
        find(l,mid,xl,yl);
    }

}