結果
| 問題 |
No.924 紲星
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2019-11-08 23:04:48 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,280 ms / 4,000 ms |
| コード長 | 6,695 bytes |
| コンパイル時間 | 4,407 ms |
| コンパイル使用メモリ | 87,328 KB |
| 実行使用メモリ | 202,760 KB |
| 最終ジャッジ日時 | 2024-09-15 02:11:51 |
| 合計ジャッジ時間 | 23,887 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 16 |
ソースコード
package contest191108;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), Q = ni();
int[] a = na(n);
long[] cum = new long[n+1];
for(int i = 0;i < n;i++)cum[i+1] = cum[i] + a[i];
Node[] rs = makeEntries(a);
for(int i = 0;i < Q;i++) {
int L = ni()-1, R = ni()-1+1;
int val = kth(rs[L], rs[R], (R-L)/2);
long minor = sumFirstK(rs[L], rs[R], (R-L)/2);
long major = cum[R] - cum[L] - minor;
out.println(major - (long)val*(R-L-(R-L)/2) + (val*((long)(R-L)/2) - minor));
}
}
public static class Node
{
public int num;
public int count;
public int des;
public long sum;
public Node left, right;
public Node(int num, int count, long sum) {
this.num = num;
this.count = count;
this.sum = sum;
des = count;
}
public Node clone()
{
Node ret = new Node(num, count, sum);
ret.left = this.left;
ret.right = this.right;
return ret;
}
public void update()
{
des = count;
sum = (long)num * count;
if(left != null){
des += left.des;
sum += left.sum;
}
if(right != null){
des += right.des;
sum += right.sum;
}
}
public Node insert(int x)
{
if(x < num){
left = left.clone();
left.insert(x);
}else if(x > num){
right = right.clone();
right.insert(x);
}else{
count++; // e is always cloned.
}
update();
return this;
}
public Node erase(int x)
{
if(x < num){
left = left.clone();
left.erase(x);
}else if(x > num){
right = right.clone();
right.erase(x);
}else{
count--; // e is always cloned.
}
update();
return this;
}
public String toString(String indent) {
StringBuilder builder = new StringBuilder();
if(left != null){
builder.append(left.toString(indent + " "));
}
builder.append("[num=");
builder.append(num);
builder.append(", count=");
builder.append(count);
builder.append(", des=");
builder.append(des);
builder.append(", sum=");
builder.append(sum);
builder.append("]\n");
if(right != null){
builder.append(right.toString(indent + " "));
}
return builder.toString();
}
}
public static long sumFirstK(Node X, Node Y, int K)
{
long alsum = 0;
while(K > 0){
Node XL = X.left, YL = Y.left;
if(XL != null && K < YL.des - XL.des){
X = XL; Y = YL;
}else{
if(XL != null){
K -= YL.des - XL.des;
alsum += YL.sum - XL.sum;
}
if(K < Y.count - X.count){
alsum += (long)Y.num * K;
break;
}else{
alsum += (long)Y.num * (Y.count - X.count);
K -= Y.count - X.count;
X = X.right; Y = Y.right;
}
}
}
return alsum;
}
public static int kth(Node X, Node Y, int K)
{
while(true){
Node XL = X.left, YL = Y.left;
if(XL != null && K < YL.des - XL.des){
X = XL; Y = YL;
}else{
if(XL != null){
K -= YL.des - XL.des;
}
if(K < Y.count - X.count){
return Y.num;
}else{
K -= Y.count - X.count;
X = X.right; Y = Y.right;
}
}
}
}
public static Node[] makeEntries(int[] a)
{
int n = a.length;
Node[] entry = new Node[n+1];
entry[0] = buildPBST(a);
for(int i = 0;i < n;i++){
entry[i+1] = entry[i].clone().insert(a[i]);
}
return entry;
}
public static Node buildPBST(int[] oa){
int n = oa.length;
int[] a = Arrays.copyOf(oa, n);
Arrays.sort(a);
int[] b = new int[n];
int p = 0;
for(int i = 0;i < n;i++){
if(i == 0 || a[i] != a[i-1]){
b[p++] = a[i];
}
}
b = Arrays.copyOf(b, p);
return dfs(0, p, b);
}
private static Node dfs(int l, int r, int[] b)
{
if(l == r)return null;
int m = l+r>>>1;
Node ret = new Node(b[m], 0, 0L);
ret.left = dfs(l, m, b);
ret.right = dfs(m+1, r, b);
return ret;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
// @Override
// public void run() {
// long s = System.currentTimeMillis();
// solve();
// out.flush();
// if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
// }
// };
// t.start();
// t.join();
}
public static void main(String[] args) throws Exception { new E().run(); }
private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private long[] nal(int n)
{
long[] a = new long[n];
for(int i = 0;i < n;i++)a[i] = nl();
return a;
}
private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[][] nmi(int n, int m) {
int[][] map = new int[n][];
for(int i = 0;i < n;i++)map[i] = na(m);
return map;
}
private int ni() { return (int)nl(); }
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}