#include #include #include #include #include #include #include // 内部定数 #define D_QUERY_MAX 100000 // 最大クエリ数 #define D_ARRAY_MAX D_QUERY_MAX * 2 // 最大配列数 #define D_SEGT_CNT 262144 // セグメントツリーデータ数(2の累乗) // 内部構造体 - クエリ情報 typedef struct Query { int miMode; // 0 or 1 int miVal1, miVal2; // 値 } Query; // 内部変数 static FILE *szpFpI; // 入力 static Query sz1Query[D_QUERY_MAX]; // クエリ static int siQCnt; // クエリ数 static int si1Array[D_ARRAY_MAX]; // 配列 static int siACnt; // 配列数 static int si1SegT[D_SEGT_CNT * 2]; // セグメントツリー static int siSCNo; // セグメントツリー - 子の開始位置 // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; static int siTNo; #endif // 出力 int fOut( char *pcpLine // 1行 ) { char lc1Buf[1024]; #ifdef D_TEST fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, pcpLine)) { siRes = -1; } #else printf("%s", pcpLine); #endif return 0; } // ソート関数 - int昇順 int fSortFnc( const void *pzpVal1 // 値1 , const void *pzpVal2 // 値2 ) { int *lipVal1 = (int *)pzpVal1; int *lipVal2 = (int *)pzpVal2; // int昇順 if (*lipVal1 > *lipVal2) { return 1; } else if (*lipVal1 < *lipVal2) { return -1; } return 0; } // 配列 - 重複カット int fCutDpl( int *pipArray // 配列 , int *pipACnt // 配列数 ) { int i; int liTo = 1; int liDCnt = 0; for (i = 1; i < *pipACnt; i++) { if (pipArray[i] != pipArray[liTo - 1]) { pipArray[liTo] = pipArray[i]; liTo++; } else { liDCnt++; } } *pipACnt -= liDCnt; return 0; } // 検索 // 戻り値:[>=0]配列番号 [-1]なし int fBSrh( int piVal // 値 , int *pipArray // 配列 , int piACnt // 配列数 ) { // 初期範囲 int liSNo = 0; int liENo = piACnt - 1; // 検索 while (1) { // 中間位置 int liMNo = (liSNo + liENo) / 2; // 一致チェック if (piVal == pipArray[liMNo]) { return liMNo; } // 範囲を絞る if (piVal < pipArray[liMNo]) { // 左側へ liENo = liMNo - 1; } else { // 右側へ liSNo = liMNo + 1; } // 範囲チェック if (liSNo > liENo) { return -1; } } return -1; } // セグメントツリー - 子の開始位置 - セット int fSegTSetCSNo( int piCnt // 子データ数 ) { siSCNo = 1; while (siSCNo < piCnt) { siSCNo *= 2; } return 0; } // セグメントツリー - 子の処理 int fSegTCProc( int piNo1 // 位置1 0~ , int piNo2 // 位置2 0~ ) { return si1SegT[piNo1] + si1SegT[piNo2]; } // セグメントツリー - 取得 int fSegTGetRngMain( int piGetS // 取得範囲 - 開始 0~ , int piGetE // 取得範囲 - 終了 0~ , int piNNo // 現在位置 1~ , int piNowS // 現在範囲 - 開始 0~ , int piNowE // 現在範囲 - 終了 0~ ) { // 内包チェック if (piGetS <= piNowS && piNowE <= piGetE) { return si1SegT[piNNo]; } // 中間位置 int liCenter = (piNowS + piNowE) / 2; int liRet = 0; // 左側 if (piGetS <= liCenter) { liRet = fSegTGetRngMain(piGetS, piGetE, piNNo * 2, piNowS, liCenter); } // 右側 if (piGetE >= liCenter + 1) { liRet += fSegTGetRngMain(piGetS, piGetE, piNNo * 2 + 1, liCenter + 1, piNowE); } return liRet; } int fSegTGetRng( int piGetS // 取得範囲 - 開始 0~ , int piGetE // 取得範囲 - 終了 0~ ) { return fSegTGetRngMain(piGetS, piGetE, 1, 0, siSCNo - 1); } // セグメントツリー - 更新 int fSegTUpOne( int piUpNo // 更新位置 0~ , int piAdd // 加算値 ) { // 子番号 int liCNo1 = siSCNo + piUpNo; int liCNo2; if (liCNo1 % 2 == 0) { liCNo2 = liCNo1 + 1; } else { liCNo2 = liCNo1 - 1; } // 更新 si1SegT[liCNo1] += piAdd; // 親を更新 while (1) { // 親番号 int liPNo = liCNo1 / 2; if (liPNo < 1) { break; } // 更新 si1SegT[liPNo] = fSegTCProc(liCNo1, liCNo2); // 次の子番号 liCNo1 = liPNo; if (liCNo1 % 2 == 0) { liCNo2 = liCNo1 + 1; } else { liCNo2 = liCNo1 - 1; } } return 0; } // 実行メイン long long fMain( ) { int i; char lc1Buf[1024]; // クエリ数・配列数 - 取得 fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &siQCnt); siACnt = siQCnt * 2; // クエリ・配列 - 取得 for (i = 0; i < siQCnt; i++) { fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d%d%d", &sz1Query[i].miMode, &sz1Query[i].miVal1, &sz1Query[i].miVal2); si1Array[i * 2] = sz1Query[i].miVal1; si1Array[i * 2 + 1] = sz1Query[i].miVal2; } // 配列 - ソート qsort(si1Array, siACnt, sizeof(int), fSortFnc); // 配列 - 重複カット fCutDpl(si1Array, &siACnt); // セグメントツリー - 子の開始位置 - セット fSegTSetCSNo(siACnt); // クエリ - 実行 long long llSum = 0; for (i = 0; i < siQCnt; i++) { int liNo1 = fBSrh(sz1Query[i].miVal1, si1Array, siACnt); if (sz1Query[i].miMode == 0) { fSegTUpOne(liNo1, sz1Query[i].miVal2); } else { int liNo2 = fBSrh(sz1Query[i].miVal2, si1Array, siACnt); llSum += fSegTGetRng(liNo1, liNo2); } } return llSum; } // 1回実行 int fOne( ) { long long llRet; char lc1Buf[1024]; // データ - 初期化 memset(si1SegT, 0, sizeof(si1SegT)); // セグメントツリー // 入力 - セット #ifdef D_TEST sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo); szpFpI = fopen(lc1Buf, "r"); sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo); szpFpA = fopen(lc1Buf, "r"); siRes = 0; #else szpFpI = stdin; #endif // 実行メイン llRet = fMain(); // 出力 sprintf(lc1Buf, "%lld\n", llRet); fOut(lc1Buf); // 残データ有無 #ifdef D_TEST lc1Buf[0] = '\0'; fgets(lc1Buf, sizeof(lc1Buf), szpFpA); if (strcmp(lc1Buf, "")) { siRes = -1; } #endif // テストファイルクローズ #ifdef D_TEST fclose(szpFpI); fclose(szpFpA); #endif // テスト結果 #ifdef D_TEST if (siRes == 0) { printf("OK %d\n", siTNo); } else { printf("NG %d\n", siTNo); } #endif return 0; } // プログラム開始 int main() { #ifdef D_TEST int i; for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) { siTNo = i; fOne(); } #else fOne(); #endif return 0; }