生活随笔
收集整理的這篇文章主要介紹了
[CQOI2015]任务查询系统(差分+主席树)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
鏈接：https://ac.nowcoder.com/acm/problem/19936
來源：牛客網
題目描述
最近實驗室正在為其管理的超級計算機編制一套任務管理系統，而你被安排完成其中的查詢部分。超級計算機中的任務用三元組(Si,Ei,Pi)描述，(Si,Ei,Pi)表示任務從第Si秒開始，在第Ei秒后結束（第Si秒和Ei秒任務也在運行 ），其優先級為Pi。同一時間可能有多個任務同時執行，它們的優先級可能相同，也可能不同。調度系統會經常向查詢系統詢問，第Xi秒正在運行的任務中，優先級最小的Ki個任務（即將任務按照優先級從小到大排序后取前Ki個 ）的優先級之和是多少。
特別的，如果Ki大于第Xi秒正在運行的任務總數，則直接回答第Xi秒正在運行的任務優先級之和。上述所有參數均為整數，時間的范圍在1到n之間（包含1和n）。
輸入描述:
輸入文件第一行包含兩個空格分開的正整數m和n，分別表示任務總數和時間范圍。
接下來m行，每行包含三個空格分開的正整數Si、Ei和Pi(Si ≤ Ei)，描述一個任務。
接下來n行，每行包含四個空格分開的整數Xi、Ai、Bi和Ci，描述一次查詢。查詢的參數Ki需要由公式 Ki=1+(AiPre+Bi) mod Ci計算得到。其中Pre表示上一次查詢的結果，對于第一次查詢，Pre=1。
輸出描述:
輸出共n行，每行一個整數，表示查詢結果。
示例1
輸入
復制
4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
輸出
復制
2
8
11
沙雕題，到最后我也不知道為什么我的是mle。。
離散化優先級之后，對于每件物品，我們在它開始的時間+1優先級，在它結束的時間后一秒-1*優先級。然后再類似于差分數組遍歷一遍求每一個時間點的優先級和。剩下的就是主席樹求前k小的優先級和的模板了。
代碼如下：
#include <bits/stdc++.h>using namespace std
;
typedef long long ll
;
const int maxn
= 1e6+9;int num
;
int dl
[maxn
],dr
[maxn
],p
[maxn
],h
[maxn
],who
[maxn
];
ll sum
[maxn
*40],cnt
[maxn
*40];
int rt
[maxn
*40],lson
[maxn
*40],rson
[maxn
*40];
int cur
;void build(int &now
,int l
,int r
,int L
,int val
){if(!now
)now
=++cur
;sum
[now
]+=1ll*val
*h
[L
];cnt
[now
]+=val
;if(l
==r
)return;int mid
=(l
+r
)>>1;if(L
<=mid
)build(lson
[now
],l
,mid
,L
,val
);else build(rson
[now
],mid
+1,r
,L
,val
);
}int rebuild(int x
,int y
){if(!x
||!y
)return x
+y
;int now
=++cur
;sum
[now
]=sum
[x
]+sum
[y
];cnt
[now
]=cnt
[x
]+cnt
[y
];lson
[now
]=rebuild(lson
[x
],lson
[y
]);rson
[now
]=rebuild(rson
[x
],rson
[y
]);return now
;
}ll
query(int now
,int l
,int r
,ll k
){if(l
==r
){return 1ll*h
[l
]*min(k
,cnt
[now
]);}int mid
=(l
+r
)>>1;if(cnt
[lson
[now
]]>=k
)return query(lson
[now
],l
,mid
,k
);else return sum
[lson
[now
]]+query(rson
[now
],mid
+1,r
,k
-cnt
[lson
[now
]]);
}int main(){int n
,m
;scanf("%d%d",&n
,&m
);for(int i
=1;i
<=n
;i
++){scanf("%d%d%d",&dl
[i
],&dr
[i
],&p
[i
]);h
[i
]=p
[i
];}sort(h
+1,h
+1+n
);num
=unique(h
+1,h
+1+n
)-h
-1;for(int i
=1;i
<=n
;i
++){who
[i
]=lower_bound(h
+1,h
+1+num
,p
[i
])-h
;}for(int i
=1;i
<=n
;i
++){build(rt
[dl
[i
]],1,num
,who
[i
],1);build(rt
[dr
[i
]+1],1,num
,who
[i
],-1);}for(int i
=1;i
<=m
;i
++){rt
[i
]=rebuild(rt
[i
-1],rt
[i
]);}int x
,a
,b
,c
;ll ans
=1;for(int i
=1;i
<=m
;i
++){scanf("%d%d%d%d",&x
,&a
,&b
,&c
);ll k
=1+1ll*(1ll*a
*ans
%c
+b
)%c
;ans
=query(rt
[x
],1,num
,k
);printf("%lld\n",ans
);}return 0;
}
努力加油a啊，(o)/~
總結
以上是生活随笔為你收集整理的[CQOI2015]任务查询系统(差分+主席树)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
