USACO 2019 - Tháng 2 - Hạng Vàng

Cow Land là một công viên giải trí đặc biệt dành cho bò, nơi chúng đi dạo, ăn cỏ ngon và ghé thăm nhiều điểm vui chơi khác nhau dành cho bò (tàu lượn bò đặc biệt nổi tiếng).

Có tổng cộng \(N\) điểm vui chơi khác nhau (\(2 \leq N \leq 10^5\)). Một số cặp điểm vui chơi được nối với nhau bởi tổng cộng \(N-1\) con đường, sao cho giữa hai điểm vui chơi bất kỳ tồn tại duy nhất một lộ trình gồm các con đường này. Mỗi điểm vui chơi \(i\) có một giá trị thích thú nguyên \(e_i\). Giá trị này có thể thay đổi trong ngày, vì một số điểm hấp dẫn hơn vào buổi sáng còn những điểm khác hấp dẫn hơn vào cuối buổi chiều.

Một con bò đi từ điểm vui chơi \(i\) đến điểm vui chơi \(j\) sẽ được trải nghiệm tất cả các điểm trên lộ trình từ \(i\) đến \(j\). Điều kỳ lạ là tổng giá trị thích thú của toàn bộ lộ trình này được tính bằng phép XOR theo bit của tất cả các giá trị thích thú trên lộ trình, bao gồm cả giá trị của điểm \(i\) và điểm \(j\).

Hãy giúp những con bò xác định giá trị thích thú của các lộ trình mà chúng dự định sử dụng trong chuyến đi Cow Land tiếp theo.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và số lượng truy vấn \(Q\) (\(1 \leq Q \leq 10^5\)). Dòng tiếp theo chứa \(e_1 \ldots e_N\) (\(0 \leq e_i \leq 10^9\)). Mỗi dòng trong \(N-1\) dòng tiếp theo mô tả một con đường bằng hai mã số nguyên của các điểm vui chơi \(a\) và \(b\) (đều nằm trong phạm vi \(1 \ldots N\)). Cuối cùng, mỗi dòng trong \(Q\) dòng cuối mô tả một phép cập nhật một trong các giá trị \(e_i\) hoặc một truy vấn giá trị thích thú của một lộ trình. Dòng có dạng 1 \(i\) \(v\) cho biết cần cập nhật \(e_i\) thành giá trị \(v\), còn dòng có dạng 2 \(i\) \(j\) là truy vấn giá trị thích thú của lộ trình nối điểm vui chơi \(i\) và \(j\).

Phân nhóm

Trong các test có tổng điểm không quá 50% số điểm, giá trị của các điểm vui chơi sẽ không thay đổi.

Dữ liệu ra

Với mỗi truy vấn có dạng 2 \(i\) \(j\), in trên một dòng giá trị thích thú của lộ trình từ \(i\) đến \(j\).

Ví dụ

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

21
20
4
20

Nguồn

USACO 2019 February Contest, Gold — Cow Land

Tác giả: Charles Bailey.

Sau bữa tiệc sinh nhật, hai anh em An và Bình được giao rửa một chồng đĩa gồm \(N\) chiếc đĩa được đánh số \(1, 2, \dots, N\). An đứng ở bồn rửa \(1\) với chồng đĩa bẩn, Bình đứng ở bồn rửa \(2\) và chờ để tráng đĩa bằng nước. Ở giữa An và Bình có một quầy để xếp những chiếc đĩa đã có xà phòng và chờ tráng nước. Ở mỗi bước, một trong hai thao tác sau cần thực hiện:

• An lấy chiếc đĩa trên cùng của chồng đĩa bẩn. Làm sạch bằng xà phòng. Sau đó xếp chiếc đĩa này vào quầy chờ tráng nước bằng một trong hai cách:
  • Xếp vào một chồng đĩa đã có trước đó trên quầy
  • Tạo một chồng đĩa mới nằm bên phải những chồng đã có trước đó.
• Bình lấy chiếc đĩa trên cùng của chồng đĩa nằm bên trái cùng của quầy chờ. Tráng bằng nước, rồi xếp lên trên cùng của chồng đĩa sạch.

Thứ tự của những chiếc đĩa rất quan trọng. Do đó mục tiêu của An và Bình là chồng đĩa sạch phải được xếp theo nguyên tắc: đĩa có số thứ tự nhỏ nằm ở dưới, đĩa có số thứ tự lớn nằm ở trên. Tuy nhiên, điều kiện này có thể không hoàn thành được cho toàn bộ \(N\) chiếc đĩa. Vậy nên, bạn hãy giúp An và Bình xác định độ dài tiền tố tối đa của chồng đĩa có thể thỏa mãn điều kiện này.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \le N \le 10^5)\)
• \(N\) dòng tiếp theo cho biết số thứ tự của các chiếc đĩa trong chồng đĩa bẩn theo chiều từ trên xuống.

Output

• In ra độ dài tiền tố lớn của chồng đĩa sao cho các đĩa sau khi rửa sạch có thể được xếp theo đúng thứ tự.

Examples

5
4
5
2
3
1

4

Farmer John không giỏi làm nhiều việc cùng lúc. Ông thường xuyên bị xao nhãng, khiến những dự án dài trở nên khó hoàn thành. Hiện tại, ông đang cố sơn một mặt của chuồng bò, nhưng cứ sơn xong một vùng hình chữ nhật nhỏ, ông lại bị phân tâm bởi việc chăm sóc đàn bò, khiến một số phần của chuồng được phủ nhiều lớp sơn hơn những phần khác.

Ta có thể mô tả mặt chuồng bò như một mặt phẳng \(x\)-\(y\) hai chiều. Trên đó, Farmer John sơn \(N\) hình chữ nhật có các cạnh song song với các trục tọa độ; mỗi hình được mô tả bằng tọa độ góc dưới bên trái và góc trên bên phải.

Farmer John muốn phủ vài lớp sơn lên chuồng để không phải sơn lại trong tương lai gần. Tuy nhiên, ông không muốn lãng phí thời gian bằng cách phủ quá nhiều lớp sơn. Hóa ra \(K\) lớp sơn là số lượng tối ưu. Thế nhưng khi nhìn vào diện tích được phủ \(K\) lớp sơn, ông không hài lòng lắm. Ông sẵn sàng sơn thêm không quá hai hình chữ nhật để cố gắng tăng diện tích này, miễn là hai hình chữ nhật ấy không giao nhau (không có chung bất kỳ phần diện tích dương nào). Lưu ý rằng ông cũng có thể quyết định không sơn thêm hình chữ nhật nào hoặc chỉ sơn thêm một hình chữ nhật nếu đó là lựa chọn tốt nhất.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\) (\(1 \leq K, N \leq 10^5\)). Mỗi dòng trong \(N\) dòng còn lại chứa bốn số nguyên \(x_1, y_1, x_2, y_2\), mô tả một vùng hình chữ nhật được sơn với góc dưới bên trái \((x_1, y_1)\) và góc trên bên phải \((x_2, y_2)\). Tất cả các giá trị \(x\) và \(y\) đều nằm trong phạm vi \(0 \ldots 200\), và mọi hình chữ nhật đều có diện tích dương.

Giống như các hình chữ nhật đã sơn, mọi hình chữ nhật mới mà Farmer John sơn đều phải có diện tích dương, đồng thời các điểm góc của chúng phải có tọa độ \(x\) và \(y\) trong phạm vi \(0 \ldots 200\).

Dữ liệu ra

In ra diện tích lớn nhất của phần chuồng có thể được phủ đúng \(K\) lớp sơn nếu Farmer John sơn thêm không quá hai hình chữ nhật không giao nhau.

Ví dụ

3 2
1 1 4 4
3 3 7 6
2 2 8 7

26

Nguồn

USACO 2019 February Contest, Gold — Painting the Barn

Tác giả: Nick Wu và Brian Dean.