結果
| 問題 |
No.510 二次漸化式
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2017-04-29 14:28:03 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 263 ms / 3,000 ms |
| コード長 | 5,926 bytes |
| コンパイル時間 | 3,893 ms |
| コンパイル使用メモリ | 87,444 KB |
| 実行使用メモリ | 65,044 KB |
| 最終ジャッジ日時 | 2024-09-13 19:14:27 |
| 合計ジャッジ時間 | 12,051 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 34 |
ソースコード
package contest170428;
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 C2 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
SegmentTreeArrayL st = new SegmentTreeArrayL(n+1);
int[] xs = new int[n];
int[] ys = new int[n];
for(int Q = ni();Q > 0;Q--){
char c = nc();
if(c == 'x'){
int id = ni(), v = ni();
xs[id] = v;
st.update(id, xs[id], ys[id]);
}else if(c == 'y'){
int id = ni(), v = ni();
ys[id] = v;
st.update(id, xs[id], ys[id]);
}else{
int id = ni();
long[] v = {1, 1, 1, 1};
out.println(st.apply(0, id, v)[0]);
}
// tr("--------------");
// for(long[] no : st.node){
// tr(no);
// }
// for(int i = 0;i < 3;i++){
// long[] v = {1, 1, 1, 1};
// tr(st.apply(0, i, v));
// }
}
}
int mod = 1000000007;
public static class SegmentTreeArrayL {
public int M, H, N;
public long[][] node;
public int K = 8;
public SegmentTreeArrayL(int n)
{
N = n;
M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
H = M>>>1;
node = new long[M][];
for(int i = 0;i < N;i++){
long[] item = new long[K];
item[5] = item[7] = 1;
node[H+i] = item;
}
for(int i = H-1;i >= 1;i--)propagate(i);
}
private void propagate(int cur)
{
node[cur] = prop2(node[2*cur], node[2*cur+1], node[cur]);
}
int mod = 1000000007;
private long[] prop2(long[] L, long[] R, long[] C)
{
if(L != null && R != null){
if(C == null)C = new long[K];
long[] P = C;
// 1 a 0 0
// 0 b c d
// 0 0 e f
// 0 0 0 1
P[0] = (L[0]+R[0]*L[3])%mod;
P[1] = (L[1]+R[0]*L[4]+R[1]*L[6])%mod;
P[2] = (L[2]+R[0]*L[5]+R[1]*L[7]+R[2])%mod;
P[3] = (R[3]*L[3])%mod;
P[4] = (R[3]*L[4]+R[4]*L[6])%mod;
P[5] = (R[3]*L[5]+R[4]*L[7]+R[5])%mod;
P[6] = (R[6]*L[6])%mod;
P[7] = (R[6]*L[7]+R[7])%mod;
return C;
}else if(L != null){
return prop1(L, C);
}else if(R != null){
return prop1(R, C);
}else{
return null;
}
}
private long[] prop1(long[] L, long[] C)
{
if(C == null)C = new long[K];
System.arraycopy(L, 0, C, 0, K);
return C;
}
public void update(int x, long a, long b) {
node[H+x][0] = a;
node[H+x][3] = b*b%mod;
node[H+x][4] = 2*b;
node[H+x][6] = b;
for(int i = H+x>>>1;i >= 1;i>>>=1)propagate(i);
}
public long[] apply(int l, int r, long[] v) {
return apply(l, r, v, 0, H, 1);
}
public long[] apply(long[] m, long[] v)
{
long v0 = (v[0] + m[0] * v[1] + m[1] * v[2] + m[2]) % mod;
long v1 = (m[3] * v[1] + m[4] * v[2] + m[5]) % mod;
long v2 = (m[6] * v[2] + m[7]) % mod;
v[0] = v0; v[1] = v1; v[2] = v2;
return v;
}
protected long[] apply(int l, int r, long[] v, int cl, int cr, int cur)
{
if(l <= cl && cr <= r){
return apply(node[cur], v);
}else{
int mid = cl+cr>>>1;
if(cl < r && l < mid){
v = apply(l, r, v, cl, mid, 2*cur);
}
if(mid < r && l < cr){
v = apply(l, r, v, mid, cr, 2*cur+1);
}
return v;
}
}
}
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 C2().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)); }
}